先来看题：

全排列题面：输入自然数N（1≤N≤9），从小到大输出1到N的所有排列，每行一个。输入2时依次输出12、21；输入3时依次输出123、132、213、231、312、321。

本题是一个经典的dfs问题，在n固定的情况下可以用几层循环解决问题，而题目中n不固定，所以要用搜索的方式解决问题。

全排列的问题是最经典的dfs问题，所以本题考的主要是dfs（深度优先搜索）的思维。

简单介绍一下dfs算法：一直往深处走，直到找到解或者走不下去为止，好比遇到一个分岔口，先随便选一条路走，例如选择了左边的路，无论结果如何都要返回这个岔路口，试探右边的路。这其中涉及到一个“回溯”的思想，即“回到岔路口”这一行为，所以我们需要用到函数的递归调用。

下面先来看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
int n;
int a[20],book[20]={0};
void dfs(int step)
{
	if(step==n)//当放入足够的数字之后，输出 
	{
		for(int i=0;i<n;i++)
		{
			printf("%d",a[i]);
		}
		printf("\n");
		return;
	}
	else
	{
		for(int j=1;j<=n;j++)
		{
			if(book[j]==0)//如果这个数字没有被用过 
			{
				book[j]=1;//标记为已用 
				a[step]=j;//将这个数子加入到排列中 
				dfs(step+1);//向更深层调用 
				book[j]=0;//将用完的数字解除标记 
			}
		}
	}
}
int main()
{
	scanf("%d",&n);//输入一个数，求他的全排列 
	dfs(0);//调用dfs函数 
	return 0;
 }
回溯，逐帧看

上方代码的确定性模型，不是在浏览器里执行 C++。

n = 3：输出 123 → 返回 dfs(2) → book[3] = 0。有效路径退回 12，a 仍是 123，末位 3 是旧值。

继续回退、选入 3：a 是 133，但有效前缀只有 13。输出依次为 123、132、213、231、312、321。

下面我来模拟一下这个流程：

首先进入主函数，接收一个n，这个n即为排列数的总数，同时也是一组数中的最大数。我们假设n=3；

step可以理解为“步数”，每走一步，相当于往排列中填进一个数字，n=3的情况下，我们一共需要走三步，在一开始调用dfs函数时，我们还一步没有走，所以dfs(0)；

进入dfs函数后，我们先要想好出函数，也就是回溯的条件，当我们step==3时，我们已经填入了三个数，输出他们，并return。注意每次进入函数后，先要判断是否满足出函数的条件。

接下来就是函数的主体部分

当n=3时，我们可以选择在一个排列中的第一个数的位置放入“1，2，3”中任意一个数字，在这里我们规定了一个循环来从小到大遍历每一位数字。

进入循环后可以发现我们利用了两个不同含义的数组

a 数组是我们储存排列用的数组。因为代码从 dfs(0) 开始，在 n=3 时，需要依次往 a[0]、a[1]、a[2] 填入数字；

而book数组是一个供我们进行判断的数组，因为全排列中，每个数字只能使用一次，可以理解为有三张卡片，卡片上分别标有1，2，3三个数字，一开始三个卡片都没有被使用过，我们规定book中的数字都为0，而只有book值为0的数才会被我们考虑填入a中，当1被使用后，我们让book[1]=1，标记为使用，下次再调用函数时就不会考虑1这个数字。

当我们发现一个合理的数字后，我们将他填入数组a中，同时令step加一，并再次进行调用dfs，考虑下一个数字。

最后是book[j]=0，即让这个数接触标记，因为他是调用完dfs的后一步，这个数字已经参与完排列并输出了，我们需要进行还原，来使这个数字之后也可以被调用。

全排列的深度优先搜索示意：首位选1，跳过已用数字，依次得到123与132，并沿箭头回溯。

 这是我用画图模拟的流程

对于2，3的模拟我就省略了，和1类似。

总结：全排列问题是一个很经典的dfs问题，对于初学者来说，递归调用是比较难理解的，比如还有一个汉诺塔问题也有异曲同工之妙（在考虑要不要写个汉诺塔呢），总之还是要多看题好好理解啊qwq~；

校订记录（2026-10-09）：本页从原文迁入后，依据示例代码将 n=3 时的数组下标说明校正为 0 至 2；原始代码和原文日期保留。