/* * 输入一个指定点的数n,输出1-n的全排列,要求n<10*/#include 
    
     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 
    
     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中扩展方法，但是并不是每种扩展都能扩展成功。