排列数字

dfs概述

$dfs$可以看做对解的空间树（搜索树）的深度优先遍历，是递归的一种形式，时间复杂度是指数级的，需要“剪枝”来避免超时

1. 剪枝

剪枝就是对明显不是答案的部分进行舍去，让这种情况不在递归下去

2. 递归的实现

递归的实现要借助栈，递归参数一般是用系统的栈，无需手写（当然也可以自己学着去写）。一些比较大的数据，比如说数组，一般定义为全局变量，自己实现栈的功能（也就是y总上课讲的要恢复现场）

3. 特点

dfs将要搜索的目标分成若干“层”，每层基于前几层的状态进行决策，直到达到目标状态

(1) 思考方式

搜索的题思考和$dp$类似，毕竟大部分$dp$问题都可以用记忆化搜索的形式来写，也就是递归来写

(2) 状态表示

在思考的时候，需要每一层的状态如何表示，包含那些数据

状态如何存储？小的数据可以放在递归参数由系统的栈存储，大的数据比如说数组，防止爆栈，我们一般开全局变量自己实现栈功能（恢复现场）

(3) 状态转移

每一层到下一层，是怎么样发生状态转移的，通过怎么样的变化可以转移

这一步要加上剪枝，即对于明显不是我们需要的答案的状态，它将不再向下转移

4. 恢复现场

有些时候，对于一些有用的信息会用于剪枝，这时候我们需要对它打上标记(st数组)或者不恢复现场

5. 递归终止条件

搜索到哪一层，我们可以输出答案

我们之前的每一步一定要向递归终止方向走，否则会出现死循环

6. dfs搜索框架

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

思路分析

本题需要按字典序进行全排列输出

1. 状态表示

对于每一层，我们是枚举它的当前位的数字

数据存储
枚举的位数和当前判重状态作为函数参数
$path$[ ]数组用来存储最终答案，数组比较大，所以放在外面

2. 状态转移

由于我们要以字典序输出，所以枚举下一位时，数字从小到大进行枚举

3. 剪枝

数字只会用一遍，所以前面枚举过的，后面将不再使用

课上y总采用的是$st$[ ]状态数组，每用一位，打上标记，本层递归转移到下一层时，每种情况$st$[ ]不一样，所以我们需要恢复现场

打卡代码中，我们采用$int$型变量$state$存储状态。把这个数字看成二进制，它的每一位表示的就是当前位的数字用过与否，本题$n<=7%, $int$有32位，也足够表示。用位运算来取出和修改本位状态

4. 递归终止条件

我们每一次都是往更高的位去转移，当转移到最高位的下一位时，也就是枚举完成之时，由于之前已经充分剪枝，这时$path$[ ]存的就是答案，直接输出就好

代码

#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; // 存储答案

void dfs(int u, int state) // u表示枚举到哪一位， state存储数字的使用情况
{
    if (u == n) // 递归结束
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]); // 输出答案
        puts("");

        return;
    }

    for (int i = 0; i < n; i ++ ) // 枚举当前的数字
        if (!(state >> i & 1)) // 该数字必须没有用过，剪枝
        {
            path[u] = i + 1; // 存储答案
            dfs(u + 1, state + (1 << i)); // 递归处理下一位， state + (1 << i)，把state的第i位置1
        }
}

int main()
{
    scanf("%d", &n);

    dfs(0, 0); // 从第0位开始枚举，初始状态是每一个数字都没用过

    return 0;
}