AcWing0092 指数级枚举
从 1∼n 这 n个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好 1个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围
1≤n≤15
(1)递归方案(DFS)
算法思想:
每个数字有不选与选两种状态,分别使用0与1表示,记录在state[i]
中。
自顶向下递归地生成状态数组:若所有数字的状态已生成,则根据状态打印相应的方案。否则,标记当前数字的状态为0,然后递归地处理下一个数字;然后标记当前数字的状态为1,递归地处理下一个数字。
C++代码段:
#include <iostream>
using namespace std;
//state[i]取值为0或1,表示不选或选择数i
// 根据state数组输出对应的方案
void printSolution(int n, bool state[]) {
for (int i = 1; i <= n; i++) {
if (state[i] == 1) {
cout << i << " ";
}
}
cout << endl;
return;
}
void generateCombinations(int n, bool state[], int i) {
// 所有数字已处理,则打印方案
if (i == n + 1) {
printSolution(n, state);
return;
}
// 不选i,然后递归地处理数字i+1
state[i] = 0;
generateCombinations(n, state, i + 1);
// 选择i,然后递归地处理数字i+1
state[i] = 1;
generateCombinations(n, state, i + 1);
}
int main() {
int n;
cin >> n;
bool state[n + 1];
generateCombinations(n, state, 1);
return 0;
}
时间复杂度:$O(n*2^n)$。这是因为,共有$2^n$种方案,每种方案有n个数字状态。
(2)状态压缩方案(非递归方案)
算法思想:
每个数字 i ($1\leq i\leq n$)有不选与选两种状态,分别使用0与1表示,可以用一位二进制位$b_{i-1}$表示。n个数字状态对应有$2^n$种组合方案,可以用n位二进制整数$b_{n-1}…b_1b_0$表示,记录在整数变量state($0\leq state< 2^n$)中。其中$b_{i-1}=state>>(i-1)$ & 1。
依次枚举$2^n$种组合方案,根据每种方案中的n位二进制位输出方案即可。
C++代码:
#include <iostream>
using namespace std;
// 输入n位二进制正整数state,打印对应的方案
void printSolution(int state, int n) {
for (int i = 1; i <= n; i++) {
bool b = state >> (i - 1) & 1;
if (b == 1) {
cout << i << " ";
}
}
cout << endl;
return;
}
// 根据输入的整数个数n,生成不同的组合数并输出
void generateCombinations(int n) {
int m = 1 << n;
for (int state = 0; state < m; state++) {
printSolution(state, n);
}
}
int main() {
int n;
cin >> n;
generateCombinations(n);
return 0;
}
时间复杂度:$O(n*2^n)$。这是因为,共有$2^n$种方案,每种方案有n个数字状态。