原文链接
DFS解决全排列问题，从一道奥数题开始说起。http://www.jianshu.com/p/897f2a9e33cd
总结
有关全排列的题目可以通过DFS来解决。
- 最简单的例子
- 题目：有数字1-9，求其全排列
- 分析：
想象有九个空位a[9]，现在第一个空位上填上一个数字，有多种选择，假设a[0] = 1；
接下来在第二个空位上继续填数字，要求不与之前填过的数字相同（用book标记），则还剩下8个数字可以选择，假设a[1] = 2；
依次类推，全部填满，打印。
之后要退回一位，恢复book标记，选择其他数字，向下填空。 - 伪代码
void dfs(int step){ //step表示当前要处理的盒子
if(step == n+1){
//输出排列
for(i = 1; i <= n; i++)
printf("%d", a[i]);
printf("\n");
return;
}
for(int i = 1; i <= n; i++){
if(book[i] == 0){
a[step] = i; //将i放入第step个空位
book[i] = 1; // i已经被使用了
dfs(step+1); //向下调用
book[i] = 0; // 非常重要，收回该空位中的数字才能进行下一次尝试。
}
}
}
- DFS框架
由上述分析，可发现过程类似DFS框架。DFS核心在于，对于每一个中可能性都尝试一遍，确定当前位的数字后，再以同样的方式调用下一位。
伪代码：
void dfs(int step){
*判断结束边界*
尝试每一种可能 for(i = 1; i <= n; i++){
尝试下一步 dfs(step + 1);
}
return;
}
- 其他变形
- 判断每一种可能——给定数组，空位选择不重复
1-9可能变形为给定数组，则同样可以通过索引和book来选择数据；此外，还可以用swap来代替book，对于给定数组，在指定位可以与后面的数字交换，同样可以实现选择的功能。
例子： [http://blog.csdn.net/ns_code/article/details/26509459 - 重复数组中有重复的，求不同的排列
额外开启一个unsorted_set用于记录当前位已经选择过的数字，如果再次遇到已经选择过的数字，则跳过。
- 判断每一种可能——给定数组，空位选择不重复
