算法六：深度优先搜索
什么是深度优先搜索？理解深度优先搜索的关键在于解决“当前如何做”，至于“下一步如何做”和“当前如何做是一样的做法”。深度优先搜索是Depth First Search, DFS。基本模型如下：
void dfs(int step){
边界判断
循环遍历去尝试每一种可能for(int i=0; i<n; i++){
继续下一步dfs(step + 1);
}
}
下面看一个实例。我们有三个数字，1，2，3.求这三个数字的所有可能的搭配。那么，答案就是123，132，213，231，312，321共6种。我给出的答案顺序，也是深度优先搜索的顺序。
假设我们有1，2，3的三张牌，地上有编号为一、二、三的三个纸箱。我们每次都把手中最小的牌放到箱子里，然后走到下一个箱子。
第一步：在一号箱子面前，放入最小的手牌1，然后前进一步。此时手牌是2和3。判断边界（手牌是否为空）。
第二步：在二号箱子面前，放入最小的手牌2，然后前进一步。此时手牌是3。判断边界（手牌是否为空）。
第三步：在三号箱子面前，放入最小的手牌3，然后前进一步，此时手牌是空。判断边界（手牌是否为空）。
第四步：手牌为空，触发边界条件。遍历打印箱子中的数字，结果是123。
第五步：取出三号箱子的牌，后退一步。此时手牌是3。
第六步：取出二号箱子的牌，此时手牌是2和3，2已经放过了，所以放3，然后前进一步。此时手牌是2。判断边界（手牌是否为空）。
第七步：在三号箱子面前，放入最小手牌2，然后前进一步，此时手牌是空。判断边界（手牌是否为空）。
第八步：手牌为空，触发边界条件。遍历打印箱子中的数字，结果是132。
第九步：取出三号箱子的牌，后退一步。此时手牌是2。
第十步：取出二号箱子的牌，此时手牌是2和3，2和3都已经放过了，所以再退一部。此时手牌是2。判断边界（手牌是否为空）。
第十一步：取出一号箱子的牌，此时手牌是1，2和3，1以及放过了，所以放剩下的最小手牌，就是2，然后前进一步，此时手牌是1，3。判断边界（手牌是否为空）。
第十二步：在二号箱子面前，放入最小的手牌1，然后前进一步。此时手牌是3。判断边界（手牌是否为空）。
第十三步：在三号箱子面前，放入最小的手牌3，然后前进一步，此时手牌是空。判断边界（手牌是否为空）。
第十四步：手牌为空，触发边界条件。遍历打印箱子中的数字，结果是213。
………………………………………………………………………………
恩，就是这样子，直接上代码了。C版本的深度优先遍历的模型。
Ps：本实例和代码均来自《啊哈！算法》一书。不过上面的过程是我自己手打原创哦^_^
#include <stdio.h>
void dfs(int step);
int a[10], book[10], n;
int main(){
//1-9的整数
scanf("%d", &n);
//从第一个箱子开始。直接从下标1开始。0不要了。
dfs(1);
}
void dfs(int step){
int i;
//已经到最后一个箱子了。
if(step == n+1){
for(i=1; i<=n; i++){
printf("%d", a[i]);
}
printf("\n");
}
//在第step个箱子面前，按照1，2，3...n的顺序一一尝试
for(i=1; i<=n; i++){
//等于0就是i还没有使用，还在手里。
if(book[i] == 0){
//使用i
a[step] = i;
//标记i已经使用
book[i] = 1;
//前进一步
dfs(step + 1);
//回收step箱子里的牌
book[i] = 0;
}
}
}