算法描述：

理解深度优先搜索的关键在于解决“当下如何做”。至于“下一步如何做”则与“当下如何做”是一样的。

以例题1为例:在这道题里边我们写的dfs(step)函数的主要功能就是解决当你在第step个盒子的时候你该怎么办。

• 通常的办法就是把每一种可能都去尝试一遍(一般使用for循环来遍历).
• 当前这一步解决后便进入下一步dfs(step+1).
• 下一步的解决方法是完全一样的.

下面给出深度优先搜索的基本模型：

void dfs(int step)
{
    判断边界
    尝试每一种可能for(int i=1;i<=n;++i)
    {
        继续下一步 dfs(step+1);
    }
    return;
}

例题：

1.啊哈!算法—P73

for(int i=1;i<=n;++i)
{
    a[step]=i;//将i号扑克牌放入到第step个盒子中
}

for(int i=1;i<=n;++i)//step表示现在站在第几个盒子面前
{
    //判断扑克牌i是否还在手上
    if(book[i]==0)//book[i]等于0表示i号扑克牌仍然在手上
    {
        a[step]=i;//将i号扑克牌放入到第step个盒子中
        book[i]=1;//将book[i]设为1，表示i号扑克牌已经不在手上
    }
}

void dfs(int step)//step表示现在站在第几个盒子面前
{
    for(int i=1;i<=n;++i)
    {
        //判断扑克牌i是否还在手上
        if(book[i]==0)//book[i]等于0表示i号扑克牌仍然在手上
        {
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1，表示i号扑克牌已经不在手上
            dfs(step+1);//这里通过函数的递归调用来实现（自己调用自己）
            book[i]=0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }
}

void dfs(int step)//step表示现在站在第几个盒子面前
{
    if(step==n+1)//如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌.
    {
        //输出一种排列(1~n号盒子中的扑克牌编号)
        for(int i=1;i<=n;++i)
            cout<<a[i]<<" ";
        cout<<endl;

        return;//返回之前的一步(最近一次调用dfs函数的地方)
    }
    for(int i=1;i<=n;++i)
    {
        //判断扑克牌i是否还在手上
        if(book[i]==0)//book[i]等于0表示i号扑克牌仍然在手上
        {
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1，表示i号扑克牌已经不在手上
            dfs(step+1);//这里通过函数的递归调用来实现（自己调用自己）
            book[i]=0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }
}

完整代码如下:

#include<iostream>
using namespace std;
int a[10],book[10],n;//此处特别说明一下，C语言的全局变量在没有赋值以前默认为0,因此这里的book数组无需全部再次赋初始值0
void dfs(int step)
{
    if(step==n+1)//如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌.
    {
        //输出一种排列(1~n号盒子中的扑克牌编号)
        for(int i=1;i<=n;++i)
            cout<<a[i]<<" ";
        cout<<endl;

        return;//返回之前的一步(最近一次调用dfs函数的地方)
    }
    //此时站在第step个盒子面前，应该放哪张牌呢？
    //按照1、2、3...n的顺序一一尝试
    for(int i=1;i<=n;++i)
    {
        //判断扑克牌i是否还在手上
        if(book[i]==0)//book[i]等于0表示i号扑克牌仍然在手上
        {
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1，表示i号扑克牌已经不在手上
            dfs(step+1);//这里通过函数的递归调用来实现（自己调用自己）
            book[i]=0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }
    return;
}

int main()
{
    cin>>n;
    dfs(1);//首先站在1号小盒子面前
    return 0;
}

2.啊哈！算法—P58

#include<iostream>
using namespace std;
int a[10],book[10],cnt=0;
void dfs(int step)
{
    if(step==10)//如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌.
    {
        //判断是否满足等式
        if(a[1]*100+a[2]*10+a[3]+a[2]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
            cnt++;

         return;//返回之前的一步(最近一次调用dfs函数的地方)
    }
    //此时站在第step个盒子面前，应该放哪张牌呢？
    //按照1、2、3...n的顺序一一尝试
    for(int i=1;i<=9;++i)
    {
        //判断扑克牌i是否还在手上
        if(book[i]==0)//book[i]等于0表示i号扑克牌仍然在手上
        {
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1，表示i号扑克牌已经不在手上
            dfs(step+1);//这里通过函数的递归调用来实现（自己调用自己）
            book[i]=0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }
    return;
}

int main()
{
    dfs(1);//首先站在1号小盒子面前
    cout<<cnt/2;//因为173+286=459与286+173=459是同一种组合，所以我们在输出的时候需要将cnt除以2.
    return 0;
}