【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;
}