这个其实就是将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;
}