全排列数字(dfs的用法1)c++

讲解

这个其实就是将n个数字分成n层，判断每一层应该是哪个数字。我们用树形图来看比较直观些。

这里树根可能是所有元素，这里我们用n=4、树根为1举例。
每次dfs只会用本条线路没有用过的数字，dfs会一直走到一条线路的底端，然后再回溯，回溯的时候要注意将状态初始化。我们走到了第一条线路的底端4，然后回溯到3判断还有没有没用过的数字，发现没有了，再回溯到2发现还有4没有用....。就是这么个流程。

易错点

• dfs(1)和dfs(0)的时候，在return的判断条件上会有所不同。
• 应该是path[u]=i而不是path[i]=i，因为u才是层数，我们是判断每一层可以是什么数字。
• 注意回溯的时候对数据进行初始化。

源码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
bool st[N];
int path[N];

void dfs(int u)
{
    if (u == n + 1)
    {
        for (int i = 1; i <= n; i ++ ) cout << path[i] << " \n"[i == n];

    }
    for (int i = 1; i <= n; i ++ )
    {
        if (!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
            path[u] = 0;
        }
    }
}

int main()
{
    cin >> n;

    dfs(1);

    return 0;
}