AcWing 92. 递归实现指数型枚举
原题链接
简单
#include <iostream>
using namespace std;
int n;
int a[20]; //储存每一种方案
bool vis[20]; //判断是否已被选中i这个位置的数字
// 当前枚举到第pos个坑,每次从start开始找数填,一共要填total个坑
void dfs(int pos, int start, int total) {
if (pos == total + 1) { //当前枚举位置到达total+1,说明已经枚举了total个,结束递归打印方案
for (int i = 1; i <= total; i ++ ) cout << a[i] << " ";
cout << endl;
return ;
}
// 选数填坑,选择的数范围是start~n
for (int i = start; i <= n; i ++) {
//if (!vis[i]) { //vis[i]为0,即位置i的数字未被选择
vis[i] = true; a[pos] = i;
dfs (pos + 1, i + 1, total);
vis[i] = false;
//}
}
}
int main() {
cout << endl;
cin >> n;
for (int i = 1; i <= n; i ++ ) //方案的种类为个数从1到n
dfs(1, 1, i);
return 0;
}