深度优先搜索

/*
 * 输入一个指定点的数n,输出1-n的全排列,要求n<10
*/
#include <iostream>

using namespace std;

int a[10];
int book[10];
int n;

void dfs(int step);

int main()
{
    cout << "Hello World!" << endl;
    cin >> n;
    dfs(1);  //站在第一个盒子前面
    return 0;
}

void dfs(int step)
{
    int i;
    if(step == n+1) //已经走完了所有的盒子
    {
        for(i = 1;i <= n;i++)
        {
            cout << a[i];
        }
        cout << endl;
        return ;
    }
    for(i = 1;i <= n;i++)
    {
        if(book[i] == 0) //手中可用的扑克牌
        {
            a[step] = i;
            book[i] = 1; //该扑克牌不再能使用
            dfs(step+1);  //往后移动了一个小盒子
            book[i] = 0; //把这张扑克牌收回
        }
    }
    return;
}

第二个题目

将1-9分别填入9个方框中，每个数字只能用一次使得等式成立。例如173+286=459就是一个合理的组合，请求出所有组合。

/*
 * 输入一个指定点的数n,输出1-n的全排列,要求n<10
*/
#include <iostream>

using namespace std;

int a[10];
int book[10];
int n;

void dfs(int step);

int main()
{
    cout << "Hello World!" << endl;
    cin >> n;
    dfs(1);
    return 0;
}

void dfs(int step)
{
    int i;
    if(step == n+1) //已经走完了所有的盒子
    {
        if(a[1]*100 +a[2]*10+a[3]+a[4]*100+a[5]*10+a[6] ==
                a[7]*100+a[8]*10+a[9])
        {
            for(i = 1;i <= 3;i++)
            {
                cout << a[i];
            }
            cout << " + ";
            for(i = 4;i <= 6;i++)
            {
                cout << a[i];
            }
            cout << " = ";
            for(i = 7;i <= 9;i++)
            {
                cout << a[i];
            }
            cout << endl;
        }
        return ;
    }
    for(i = 1;i <= n;i++)
    {
        if(book[i] == 0) //手中可用的扑克牌
        {
            a[step] = i;
            book[i] = 1; //该扑克牌不再能使用
            dfs(step+1);  //往后移动了一个小盒子
            book[i] = 0; //把这张扑克牌收回
        }
    }
    return;
}

笔记
深度优先搜索的关键在于解决“当下该如何做”。至于“下一步如何做”则与“当下该如何做”是一样的。
下面的代码是深度优先搜索的模型

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

每一种尝试就是一种扩展。每一次站在一个盒子面前的时候，其实都有n中扩展方法，但是并不是每种扩展都能扩展成功。