输入一个数 \(n\)，输出 \(1\sim n\) 的所有全排列，每个排列占一行，每个字符保留 \(5\) 个场宽。勤奋的同学一定已经开始打表了是吧。
说是能做肯定不是骗大家，那怎么做呢~
其实回溯法本质还是递归，回想我们做过的小兔子（青蛙）跳台阶的那题，只是需要算出总的方案数就可以，但是这个需要你来输出具体的排列这就需要你来保留每一层递归的状态，所以我们用一个全局数组来完成这一工作（暂且命名为stack，大家可以查一查这个单词什么意思）。
以 \(n=3\) 为例，一开始stack 是空的，我们需要枚举从 \(1\) 到 \(n\) 这几个数字，填充到 stack[0] 里：
| \(\Downarrow\) | ||
|---|---|---|
| 1 |
OK 放进去了，然后考虑后面一个数字，还是从 \(1\) 到 \(n=3\) 枚举：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 1 |
大家觉得这样行吗？
——你这都跟前面重复了肯定不行啊！
不行是吧，那就换一个 \(2\)：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 2 |
OK 舒服了，再看下一个（我已经试过了，放 \(1\) 不行，\(2\) 也不行，那就放 \(3\)）：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 2 | 3 |
好的，看看下一个……哎呦怎么满了，那就输出一下叭：
此时你的控制台输出：
1 2 3
好的我们把 \(3\) 拿掉，往回退一层：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 2 |
这个 \(2\) 不是从 \(1\) 枚举过来的吗，那还没有枚举完，就还要继续枚举下去：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 3 |
好的进入下一层从 \(1\) 开始枚举：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 3 | 1 |
不行，跟前面重复了，换 \(2\) 试试：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 3 | 2 |
好像可以，stack 又满了诶，输出一下：
1 2 3
1 3 2
再把最后一个元素试图换一下 \(3\)：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 3 | 3 |
不行，死心了，往回退：
| \(\Downarrow\) | ||
|---|---|---|
| 1 | 3 |
呃，第二个元素也举到 \(3\) 了，不能继续举了，只能再退一层，把 \(1\) 换成 \(2\) 试试：
| \(\Downarrow\) | ||
|---|---|---|
| 2 |
没啥问题，再放下一个，从 \(1\) 开始枚举：
| \(\Downarrow\) | ||
|---|---|---|
| 2 | 1 |
也没有重复的，再下一个：
| \(\Downarrow\) | ||
|---|---|---|
| 2 | 1 | 1 |
最后一个放 \(1\) 行吗？不行，重复了。
| \(\Downarrow\) | ||
|---|---|---|
| 2 | 1 | 2 |
最后一个放 \(2\) 也重复了。
| \(\Downarrow\) | ||
|---|---|---|
| 2 | 1 | 3 |
那就放 \(3\)，一看可以，输出一下：
1 2 3
1 3 2
2 1 3
接下来就是周而复始的过程，直到全部都枚举完，你的输出应该是这样的：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
我们习惯上把上面的递归过程叫做 \(DFS(Depth-First-Search)\)，中文叫“深度优先搜索”，就是在一层递归里面有一个循环，每个循环还要跑一个递归，关于 \(DFS\) 在数据结构的“图 \((Graph)\)” 部分也会有讲。用“伪代码”（新词汇又来了hhh）描述这个递归是这样的：
- 参数
len是进入递归之前stack的有效长度，所以最开始调用的时候len应该是 0； -
stack和n被定义为全局变量。
void dfs(int len) {
if (len == n) {
输出 stack;
return;
}
for (int i = 1; i <= n; i++)
if (i 与 stack[0] 到 stack[len - 1] 的元素都不重复) {
stack[len] = i;
dfs(len + 1);
}
}
对于某一层递归，进入之前已经填充了 len 个，所以检查重复的时候只要从 stack[0] 检查到 stack[len - 1]。
可以想见在运行的时候这个 stack 应该是不断伸伸缩缩的，但是在退回上一层的时候并没有删除后面的元素（反正留在那也不影响，因为检查重复是到下标 len - 1，后面的不会被访问到）。
在 main() 函数里只需要这么写：
int main() {
scanf("%d", &n);
dfs(0);
// 没错我的代码可以很潇洒
return 0;
}
然后再把“输出 stack”翻译一下：
void print_stack() {
for (int i = 0; i < n; i++) {
printf("%5d", stack[i]);
}
puts("");
}
翻译一下“i 与 stack[0] 到 stack[len - 1] 的元素是否重复”，顺序查找，找到了返回 1，找不到返回 0：
int find_in_stack(int key, int len) {
for(int i = 0; i < len; i++) {
if (key == stack[i])
return 1;
}
return 0;
}
大功告成，奉上完整代码：
#include <stdio.h>
int n;
int stack[10];
void print_stack();
void dfs(int len);
int find_in_stack(int key, int len);
int main() {
scanf("%d", &n);
dfs(0);
// 没错我的代码可以很潇洒
return 0;
}
void dfs(int len) {
if (len == n) {
print_stack();
return;
}
for (int i = 1; i <= n; i++)
if (!find_in_stack(i, len)) {
stack[len] = i;
dfs(len + 1);
}
}
void print_stack() {
for (int i = 0; i < n; i++)
printf("%5d", stack[i]);
puts("");
}
int find_in_stack(int key, int len) {
for(int i = 0; i < len; i++)
if (key == stack[i])
return 1;
return 0;
}