【acwing】92. 递归实现指数型枚举

穿越隧道

递归枚举、位运算

方法① 从1到n，顺序访问每位数，是否选择，每位数有两种状态，选1或不选0.
AC代码如下：

#include <iostream>
using namespace std;const int N = 100;
// bool st[N];
int n;void dfs(int u, int state){if (u == n) {for (int i = 0; i < n; i++) {if (state >> i & 1) { // 将state移到当前第i位，判断第i位的数是否被选，被选则为1，否则为0.cout << i + 1 << " ";}}puts("");return ;}dfs(u + 1, state);dfs(u + 1, state | 1 << u); // 1.先执行 1 << u; 将1左移u位,假如u=2，移完后的值为100;然后将100和state进行或运算。表明在第u为的值为1，选这个数
}int main(){cin >> n;dfs(0, 0);return 0;
}

方法② 递归搜索数的方式 (手动模拟) ：从1开始，顺序访问每位数，是否选择，每位数有两种状态，选1或不选0.
当从1开始，不选1的时候。此时的根节点就为下一个数2，以此下去。

AC代码如下：

#include <iostream>
using namespace std;const int N = 20;
int n;
bool st[N]; void dfs(int u){if (u == n + 1) {for (int i = 1; i <= n; i++){if(st[i]){cout << i << " ";}}puts("");return ;}st[u] = true; // 选做当前u的这个分支dfs(u + 1);st[u] = false; // 不选当前u的这个分支dfs(u + 1);
}int main(){cin >> n;dfs(1);return 0;
}

方法③ 稍微复杂版。
AC代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;
const int N = 5e5 + 10;
int path[N];
bool st[N];
int n;
void dfs(int u, int start, int depth){if (u == depth + 1) {for (int i = 1; i < u; i++) {cout << path[i] << " ";}puts("");return ;}for (int i = start; i <= n; i++) { // i 从start开始，为了保证升序。if (!st[i]) {st[i] = true;path[u] = i;dfs(u + 1, i, depth);st[i] = false;}}
}int main(){cin >> n;for (int i = 0; i <= n; i++) {dfs(1,1,i); // 第一位数：树的深度，表明树深为1;第二位数：表明从1开始选；第三位数：表明树的实际深度。}return 0;
}