DFS爆搜入门

• 递归（DFS）实现指数级枚举

#include<iostream>
using namespace std;

const int N = 20;
int st[N]; // 0表示未考虑，1表示不选，2表示选
int n;

void dfs(int x){ // 枚举到第x个数字，选或者不选

    if(x > n){
        for(int i = 1; i <= n; i++)
            if (st[i] == 2) cout << i << " ";
        cout << endl;
        return ;
    }

    st[x] = 1; // 不选x
    dfs(x + 1);
    st[x] = 0; // 恢复现场，可以根据递归搜索树判断是否需要回溯

    st[x] = 2; // 选x
    dfs(x + 1);
    st[x] = 0; // 恢复现场，可以根据递归搜索树判断是否需要回溯
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

• 递归（DFS）实现排列型枚举

#include<iostream>
using namespace std;

const int N = 15;
int path[N]; // 记录每一种排列方案
bool st[N]; // 表示某数字是否用过，0表示没用过，1表示用过
int n;

void dfs(int x){ // 遍历到第x个位置，选哪一个数字
    if (x > n){
        for (int i = 1; i <= n; i++)
            printf("%5d", path[i]); // 输出场宽为5
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++){
        if (!st[i]){
            st[i] = true, path[x] = i; // 如果i没用过，第x个位置就可以放i
            dfs(x + 1);
            path[x] = 0, st[i] = false; // 恢复现场，可以根据递归搜索树判断是否需要回溯
        }
    }
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

• 递归（DFS）实现组合型枚举

#include<iostream>
using namespace std;

const int N = 15;
int path[N]; // 记录每一种排列方案
int n, k;

void dfs(int x, int start){ // 遍历到第x个位置，并且从数字start开始选择
    if (x > k){
        for (int i = 1; i <= k; i++)
            printf("%3d", path[i]); // 输出场宽为3
        cout << endl;
        return;
    }
    for (int i = start; i <= n; i++){
        path[x] = i;
        dfs(x + 1, i + 1); // 为了实现不重复，要求只从比上一个数字大的开始遍历
        path[x] = 0; // 恢复现场，可以根据递归搜索树判断是否需要回溯
    }
}

int main(){
    cin >> n >> k;
    dfs(1, 1);
    return 0;
}