842. 排列数字

基本思路

DFS主要就是明确搜索的顺序，这题搜索的顺序很简单，直接按位搜索即可。

DFS参数，回溯，恢复现场的本质：
1. DFS其实就是递归搜索树，层层进入，层层回溯
2. 如果变量在DFS的参数里，那么变量会跟着一起回溯，是系统栈帮我们自动回溯的
3. 如果变量不在DFS的参数里，那么当然变量就不会自动回溯了，所以如果你需要回溯的话，可以自己手动回溯
4. 恢复现场实际就是 变量 回溯到当前层的时候 变量 要恢复到当前层未修改时的状态
所以是否恢复现场就取决于 你是否想让当前层恢复到未修改时的状态
经验之谈：外部搜索（多个分支）需要恢复现场 内部搜索（单个分支）不需要恢复现场
5. 变量恢复现场 要满足两点 1. 变量需要回溯到当前层 2. 当前层最终变量没有修改 手动回溯一定满足这两点，自动回溯可能不满足第二点

以全排列为例分析，首先明确全排列问题，搜多个分支，为了防止污染其他分支，肯定是要恢复现场的
1. 版本1，state没有作为DFS的参数，肯定是要手动回溯的，满足恢复现场
2. 版本2，state还是没有作为DFS的参数，只是进行了状态压缩，和版本1一样，需要手动回溯，满足恢复现场
3. 版本3，state作为DFS的参数，自动回溯了，并且当前层state没有改变，满足恢复现场
4. 版本4，state作为DFS的参数，自动回溯了，但是当前层的state改变了，所以自动回溯无法恢复现场，所以还是手动回溯恢复现场

参考代码

// 1. 最直接版本
#include <iostream>
using namespace std;

const int N = 10;

int n;
int path[N];   //保存方案
bool st[N];    //状态数组

void dfs(int u)  //u代表DFS的当前层的信息 位置
{
    if(u == n)    //递归边界
    {
        for(int i=0; i<n; i++) cout << path[i] << ' ';   //输出当前方案
        puts("");
        return;
    }

    for(int i=1; i<=n; i++)    //当前位可以填哪些数
    {
        if(!st[i])             //没有被用过的数
        {
            path[u] = i;
            st[i] = true;      //i被用过
            dfs(u+1);          //DFS进入下一层      
            st[i] = false;     //手动回溯 恢复现场
            //这里path不需要手动回溯，因为其他分支可以完全覆盖它
        }
    }
}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}

// 2. 状态压缩
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];
int state;

void dfs (int u) {
    if (u == n) {
        for (int i = 0; i < n; ++ i) cout << path[i] << ' ';
        cout << endl;
        return;
    }


    for (int i = 1; i <= n; ++ i) {

        if (!(state >> i & 1)) {
            path[u] = i;
            state += (1 << i);  //当前层的状态改变了
            dfs(u + 1);
            state -=(1 << i);  //手动回溯 恢复现场
        }
    }
}

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

// 3. 状态压缩 + state 局部变量
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];

void dfs (int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; ++ i) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; ++ i) {   //当前位可以填哪些数
        //状态压缩优化空间
        if (!(state >> i & 1)) {
            path[u] = i;
            dfs(u + 1, state + (1 << i));
            //我们在每层里面没有修改过state，自动回溯就可以满足恢复现场
        }
    }
}

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

// 4. 状态压缩 + state局部变量
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];

void dfs (int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; ++ i) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; ++ i) {  
        if (!(state >> i & 1)) {
            path[u] = i;
            state += (1 << i);
            dfs(u + 1, state);
            state -= (1 << i);
            //因为在每层里面我们还是修改过state，自动回溯后还是不满足，所以自己手动回溯
        }
    }
}

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

Reference

[1]. yxc
[2]. AcWing 842. 排列数字–深度优先遍历代码+注释
[3]. AcWing 842. 排列数字—本文主要阐述代码中递归的思想！
[4]. Bug-Free 位运算代码