全排列 DFS

简单题学 dfs

题目描述

给定一个整数n，将数字1 ~ n 排成一排，将会有很多种方法。
现在按照字典序将所有的排列方法输出
样例输入：

3

样例输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题思路

如何用dfs 解决全排列问题？
注意： dfs 最重要的是搜索顺序。
对于全排列问题， 以 n = 3为例，可以这样进行搜索：

假设有三个空位，从前往后填数字，每次填一个位置，填的数字不能和前面的一样。

开始的时候，三个空位都是空的：__ __ __

首先填写第一个空位，第一个空位可以填 1，填写后为：1 __ __

填好第一个空位，填第二个空位，第二个空位可以填 2，填写后为：1 2 __

填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为： 1 2 3

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ，没有其他数字可以填。

因此再往后退一步，退到了状态：1 __ __。第二个空位上除了填过的 2，还可以填 3。第二个空位上填写 3，填写后为：1 3 __

填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为： 1 3 2

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：1 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。

因此再往后退一步，退到了状态：1 __ __。第二个空位上除了填过的 2，3，没有其他数字可以填。

因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，还可以填 2。第一个空位上填写 2，填写后为：2 __ __

填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：2 1 __

填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为：2 1 3
这时候，空位填完，无法继续填数，所以这是一种方案，输出。

剩下的以此类推哦~

代码实现

变量的说明：
用path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
用st 数组表示数字是否用过。当st[i]为true 时，i 已经被用过了，st[i] 为 false 时，i 没被用过。
dfs(i) 表示的含义是：在path[i] 处填写数字，然后递归的在下一个位置填写数字。
回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。

#include<iostream>

using namespace std;

const int N = 10;
int n;
int path[N]; // 保存序列
bool st[N]; //判断数字是否用过

void dfs(int u)
{
    
    if (n == u)  //数字填完，输出
    {
    
        for (int i = 0; i < n; i++) printf("%d ",path[i]);
             puts(""); 
            return;
    }

      
    for (int i = 1; i <= n; i++)
    {
    
        if (!st[i])
        {
    
            path[u] = i; // 放入空位置
            st[i] = true; // 数字备用修改状态
            dfs(u + 1); // 填写下一个位置
            path[u] = 0; // 回溯之前可以将空位置设置为0
            st[i] = false; // 回溯取出i
        }
    }
}

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