[AcWing]842. 排列数字（C++实现）dfs模板题，递归思想的解释

递归的难度在于理解递归是如何回退的。

1. 题目

2. 读题（需要重点注意的东西）

思路：
---------------------------------------------------dfs的思想---------------------------------------------------

dfs深度优先遍历的思想比较简单，就是一条路走到底，走到最深点处再回退一步，再看有没有路可以走，没有的话再回退一步，重复此步骤；

dfs的思想比较简单，在此不在过多的赘述，解释代码中实现dfs的递归方法，是本文的主要目的。
---------------------------------------------------递归的思想---------------------------------------------------
递归在于不断调用自己的函数，层层深入，直到遇到递归终止条件后层层回溯，其思想与dfs的思想不谋而合；因此，可以使用递归来实现dfs。
递归的进入比较容易理解，但是递归的回溯是在计算机底层执行的，我们无法看到。因此，递归究竟是如何完成的，成为了理解递归的一大难点，也是理解递归的唯一一个难点。
让我们来看一下这样一个简单的递归程序

#include<iostream>
using namespace std;

int n;

void func(int u){
    if(u == 0) return;
    cout << "Recursive program goes to the next level --- " << u << endl;
    func(u-1);
    cout << "Recursive program backtracking --- " << u <<endl;
    return;
}
int main(){
    cin >> n;
    func(n);
    return 0;
}

输入3，我们可以看到，它的输出是

我们可以清楚的看到，哪个数字进入了递归，又有哪个数字回溯了。
为什么会产生这样的结果？请看下面这幅图，它解释了递归函数的调用全过程

这样，我们就能理解，为什么首先输出的是Recursive program backtracking — 1了

如果还不是很理解，请看下面的图，我们从u = 0 回退到了u = 1，再直接回退到u = 2，再回退到u = 3

递归程序在回退完成前，return会使得计算机继续依次执行上一层函数调用后的代码。

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; // 用path数组保存路径上的值

void dfs(int u, int 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]中
        {
            path[u] = i + 1; 
            dfs(u + 1, state + (1 << i));  // 进入下一层
        }
}

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

    dfs(0, 0);

    return 0;
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

dfs模板题，推荐完全背下来。递归的思想也要好好的理解并掌握。