搜索
简帛阁>技术文章>【题解】AcWing 92.递归实现指数型枚举

【题解】AcWing 92.递归实现指数型枚举

AcWing 92.递归实现指数型枚举

题目描述

从 1 ∼ n 1∼n 1∼n 这 n n n 个整数中随机选取任意多个,输出所有可能的选择方案。

输入格式

输入一个整数 n n n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列,相邻两个数用恰好 1 1 1 个空格隔开。

对于没有选任何数的方案,输出空行。

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围

1 ≤ n ≤ 15 1≤n≤15 1≤n≤15

输入样例

3

输出样例

3
2
2 3
1
1 3
1 2
1 2 3

题目分析

我们可以用一个 n n n 位二进制数来表示一个有 n n n 个元素的集合中的一种选取情况。譬如在集合 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5} 中, 10110 10110 10110 可代表选 1 , 3 , 4 1,3,4 1,3,4 的情况。而为了得到所有的情况,我们可以枚举所有的二进制数。

代码 (枚举二进制数):

#include <iostream>
using namespace std;
int n, num[20];

int main(){<!-- -->
    cin >> n;
    for (int i = 0; i < n; i ++) num[i] = i + 1;
    
    for (int i = 0; i < 1 << n; i ++){<!-- -->
        for (int j = 0; j < n; j ++)
            if (i >> j & 1)
                cout << num[j] << " ";
        cout << endl;
    }
}

当然,我们也可以用递归方式实现指数型枚举。对于每一个数,它有两种选择:选或不选。每次递归分别尝试两条分支,将尚未确定的整数数量减 1 1 1,从而转化为规模更小的同类问题。

代码 (递归):

#include <iostream>
#include <vector>
using namespace std;
int n;
vector <int> num;

void work(int x){<!-- -->
    if (x == n + 1){<!-- -->
        for (int i = 0; i < num.size(); i ++)
            cout << num[i] << " ";
        cout << endl;
        return;
    }
    num.push_back(x);  //选第x个数
    work(x + 1);
    num.pop_back();  //回溯,不选第x个数
    work(x + 1);
}

int main(){<!-- -->
    cin >> n;
    work(1);
}
题目:从1∼n这nn个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数nn。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案
AcWing92递归实现指数枚举题目描述从1∼n1∼n1∼n这nnn个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数nnn。输出格式每行输出一种方案。同一行内的数必须升序排列
这个系列是蓝桥杯的训练,为了蓝桥杯,同时也是日常的算法训练。第一题是递归,有点类似递归的全排列的做法,复习基本的递归模板。ProblemimportjavaioBufferedReader;impor
题目描述从1~n这n个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案,
AcWing92递归实现指数枚举(深搜)写在前面:AcWing是由北大一神级人物——“大雪菜”创办的算法交流社区,里面除了正常oj网站的功能之外,还提供单人训练、双人匹配、云端操作系统等模式,除此之
AcWing92递归实现指数枚举(遍历)写在前面:AcWing是由北大一神级人物——“大雪菜”创办的算法交流社区,里面除了正常oj网站的功能之外,还提供单人训练、双人匹配、云端操作系统等模式,除此之
递归实现指数枚举题目从1~n这n个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有
题目:把1∼n这n个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,
题目:从1∼n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式:两个整数n,m,在同一行用空格隔开。输出格式:按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的数升序排列,相邻两个数
AcWing94递归实现排列枚举题目描述把1∼n1∼n1∼n这nnn个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数nnn。输出格式按照从小到大的顺序输出所有方案,每行111个。