题目链接
可以通过参考一道例题来加深对dfs的认知和学习
题意描述
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数
字序列中不允许出现重复的数字。
输出格式
由 1 ∼ n 组成的所有不重复的数字序列，每行一个序列。每个数字保留 5 个场宽。
- 数据范围 ：1<= n <= 9
题目分析
输入 ：
1
输出 ：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
观察输出样例可知，5个场宽输出的意思是每个数输出时占5个位置且右对齐，就是以
" %5d "格式输出
接着分析题目，求全排列，其实可以深搜，也就是dfs。
解题思路
算法分析
我们以 n = 3 为例，可以构造一颗搜索树来进行搜索。
如图所示 ：对一个位置进行查找，把之前没有用过的数填上去，接着对下一个位置进行
相同操作，知道每个位置填满数为止。
程序实现
我们总结一下在上一部分中的思路在程序中如何实现。
先定义两个数组，一个是用来存放解的，一个是用来标记该数是否用过。
我们可以先写一个用于打印的函数print()，每当深搜时找到一个符合条件的解时，则
print()一下，输出这个解（注意题目输出要求）。
接下来就是写深搜的函数了。主要思路：先判断格子是否填满了，如果填满，则print()一下。
如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填
入，搜索下一格。
代码如下
#include <iostream>
using namespace std;
const int N = 10;
int n;
int a[N];
bool q[N];
void dfs(int x){
if(x == n){
for(int i = 0 ; i < n ; i++)
printf("%5d",a[i]);
puts("");
}
for(int i = 1 ; i <= n ; i++){
if( !q[i] ){
a [x] = i;
q[i] = true ;
dfs(x+1);
q[i] = false ;
a[x] = 0;
}
}
}
int main()
{
cin >> n ;
dfs(0);
return 0;
}