深度搜索，就是先访问节点的某一个子节点，然后一直找子节点的某个子节点，直到没有子节点，再回到父节点访问其其他的子节点。深度搜索往往借助堆来实现。该方法常用来解决路径问题，图的连通性问题，排列组合问题等。从子节点回到父节点重新进行搜索的过程，可以叫做回溯，回溯是从某个状态返回到上一个状态，比如走到路的尽头后返回上一个分叉口。

例题

        题1：在一张6x6的地图中，分布着8块石头（如下图），某人需要从A点走到B点，有石头的点不能走，且只能向下走与向右走，请打印所有可能路径。

        分析：首先，这是一个典型的求路径问题，可以用深度或广度搜索（参考广度搜索与剪枝），这里使用深度，先定义可走的情况，由于只能往下和往右走，可以用一个数组来表示可选的下一个子节点， 因此代码主要逻辑就是遍历可走的下一个节点，记录路径，然后递归进入，错误则返回，抹掉记录的路径，再继续选择别的节点，直到成功则打印路径。

#include <iostream>
#include <string>
#include <vector>
#include <random>
using namespace std;

//地图，石头是1
int world[6][6] = {0};
//保存走过的路径
vector<pair<int,int>> path;
//可以走的2种可能性
pair<int,int> go[2] = {pair<int,int>(0,1),pair<int,int>(1,0)};

//打印路径
void printpath() {
    for (size_t i = 0; i < path.size(); i++)
    {   
        if (i > 0)
            cout << "->";
        
        cout << "(" << path[i].first << "," << path[i].second << ")";
    }
    cout << endl;
}

void search(int step) {
    pair<int, int> last = path[step-1];
    for (size_t i = 0; i < 2; i++)
    {
        int x = last.first+go[i].first;
        int y = last.second+go[i].second;
        //判断是否可走
        if (x < 6 && y < 6 && world[x][y] == 0)
        {
            //走一步
            path.emplace_back(pair<int, int>(x, y));
            if (x == 5 && y == 5) //到达终点
                printpath();
            else
            {
                step++; //未到达终点则继续搜索下一步
                search(step);
            }
            //回溯
            step--;
            path.pop_back();
        }
    }
}

int main() {
    world[0][1] = 1;
    world[1][4] = 1;
    world[2][0] = 1;
    world[2][2] = 1;
    world[3][3] = 1;
    world[3][4] = 1;
    world[4][0] = 1;
    world[4][2] = 1;
    
    //第一步从0，0开始
    path.emplace_back(pair<int, int>(0, 0));
    search(1);
    return 0;
}
输出：
(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)
(0,0)->(1,0)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)->(5,5)

        题2：给定一些数字，打印他们所有可能的排列组合。

        分析：这一题可以使用多重循环去解，也可以使用递归与回溯解，这里讲第二种，首先可以肯定需要有一个标识来记录哪些数字是用过了，接着我们在剩下的数字中去挑选，可以把所有可选数字当成一张完全连通图，所有的数都可以是任意数的下一个节点，这样一来就可以转换成使用深度遍历去解。

#include <iostream>
#include <string>
using namespace std;

int arr[7] = {3,6,9,3,8,0,1};
int flag[7] = {0};
int rst[7];

//选第n个数
void choose(int n) {
    //从7个数中选
    for (int i = 0; i < 7; i++)
    {
        if (flag[i] != 1)
        {
            rst[n] = arr[i]; //选中的转成字符串
            flag[i] = 1; //i被选过了
            //判断是否选完
            if (n == 6)
            {
                for (auto& j : rst)
                    cout << j;
                cout << endl;
            }
            else
                choose(n+1); //否则继续选下一个数
            flag[i] = 0;
        }
    }
}

int main () {
    choose(0);
    return 0;
}

        这样写有一个问题，所有组合会出现2次，比如0133689会输出2次，为什么，因为代码不认为3和3是一样的，只是机械地从他们两中随机选一个，解决方案之一是记录下最终的字符串，输出过的就不再输出。

        题3：如下图，尝试使用一笔画来经过所有的边，并打印路径。

        分析：所谓一笔画，意思就是不重复地经过所有的边，一笔画有一个技巧，就是需要从奇数边的点（奇点）出发，因为奇点由于边不是偶数的，不能进出对应，所以只能是一笔画的起点或终点。 一笔画另一个特征就是奇点只能有0个或者2个，否则无解。

        我们可以先统计下有几个奇点，确保有解的情况下，再从奇点开始遍历（若有），否则就按普通遍历的方式去遍历。可以使用二维数组 line[1][2] = 1来表示点1和点2之间是联通的。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int line[11][11] = {0}; //记录连线
vector<int> path; //记录路径
int walked; //画过的线数量

void toline(int n, int m) {
    line[n][m] = 1;
    line[m][n] = 1;
}

//找所有奇点
void findoddpoint(vector<int>& vec) {
    for (int i = 1; i < 11; i++)
    {   
        int num = 0;
        for (int j = 1; j < 11; j++)
        {
            if (line[i][j] == 1)
                num++;
        }
        if (num%2 == 1)
            vec.emplace_back(i);
    }
}

void draw(int i) {
    for (int j = 1; j < 11; j++)
    {
        if (line[i][j] == 1)
        {
            line[i][j] = 0; //断开两点连接
            line[j][i] = 0;
            path.emplace_back(j); //记下路径
            walked++;
            //所有线都画过了
            if (walked == 13)
            {
                //打印路径
                for (size_t i = 0; i < path.size(); i++){
                    if (i != 0)
                        cout << "->";
                    cout << path[i];
                }
                cout << endl;
            }else{
                draw(j); //继续找下一个点
            }
            //恢复原状
            walked--;
            path.pop_back();
            line[j][i] = 1;
            line[i][j] = 1;
        }
    }
}

int main () {
    toline(1, 2);
    toline(1, 4);
    toline(2, 3);
    toline(3, 4);
    toline(3, 5);
    toline(3, 7);
    toline(4, 8);
    toline(4, 10);
    toline(5, 6);
    toline(6, 7);
    toline(7, 8);
    toline(8, 9);
    toline(9, 10);

    vector<int> vec;
    findoddpoint(vec);
    
    if (vec.size() == 0)
    {
        //不会进来，省略，与下面相似
    }
    else if (vec.size() == 2)
    {
        for (int i = 0; i < vec.size(); i++)
        {   
            walked = 0;
            path.clear();
            path.emplace_back(vec[i]); //出发点
            draw(vec[i]);
        }
    }
    else
        cout << "无解" << endl;
    return 0;
}
输出结果：
7->3->2->1->4->3->5->6->7->8->4->10->9->8
7->3->2->1->4->3->5->6->7->8->9->10->4->8
7->3->2->1->4->8->7->6->5->3->4->10->9->8
7->3->2->1->4->8->9->10->4->3->5->6->7->8
7->3->2->1->4->10->9->8->4->3->5->6->7->8
7->3->2->1->4->10->9->8->7->6->5->3->4->8
7->3->4->1->2->3->5->6->7->8->4->10->9->8
7->3->4->1->2->3->5->6->7->8->9->10->4->8
7->3->4->8->7->6->5->3->2->1->4->10->9->8
7->3->4->8->9->10->4->1->2->3->5->6->7->8
7->3->4->10->9->8->4->1->2->3->5->6->7->8
7->3->4->10->9->8->7->6->5->3->2->1->4->8
7->3->5->6->7->8->4->1->2->3->4->10->9->8
7->3->5->6->7->8->4->3->2->1->4->10->9->8
7->3->5->6->7->8->9->10->4->1->2->3->4->8
7->3->5->6->7->8->9->10->4->3->2->1->4->8
7->6->5->3->2->1->4->3->7->8->4->10->9->8
7->6->5->3->2->1->4->3->7->8->9->10->4->8
7->6->5->3->2->1->4->8->7->3->4->10->9->8
7->6->5->3->2->1->4->8->9->10->4->3->7->8
7->6->5->3->2->1->4->10->9->8->4->3->7->8
7->6->5->3->2->1->4->10->9->8->7->3->4->8
7->6->5->3->4->1->2->3->7->8->4->10->9->8
7->6->5->3->4->1->2->3->7->8->9->10->4->8
7->6->5->3->4->8->7->3->2->1->4->10->9->8
7->6->5->3->4->8->9->10->4->1->2->3->7->8
7->6->5->3->4->10->9->8->4->1->2->3->7->8
7->6->5->3->4->10->9->8->7->3->2->1->4->8
7->6->5->3->7->8->4->1->2->3->4->10->9->8
7->6->5->3->7->8->4->3->2->1->4->10->9->8
7->6->5->3->7->8->9->10->4->1->2->3->4->8
7->6->5->3->7->8->9->10->4->3->2->1->4->8
7->8->4->1->2->3->5->6->7->3->4->10->9->8
7->8->4->1->2->3->7->6->5->3->4->10->9->8
7->8->4->3->5->6->7->3->2->1->4->10->9->8
7->8->4->3->7->6->5->3->2->1->4->10->9->8
7->8->9->10->4->1->2->3->5->6->7->3->4->8
7->8->9->10->4->1->2->3->7->6->5->3->4->8
7->8->9->10->4->3->5->6->7->3->2->1->4->8
7->8->9->10->4->3->7->6->5->3->2->1->4->8
8->4->1->2->3->4->10->9->8->7->3->5->6->7
8->4->1->2->3->4->10->9->8->7->6->5->3->7
8->4->1->2->3->5->6->7->3->4->10->9->8->7
8->4->1->2->3->5->6->7->8->9->10->4->3->7
8->4->1->2->3->7->6->5->3->4->10->9->8->7
8->4->1->2->3->7->8->9->10->4->3->5->6->7
8->4->3->2->1->4->10->9->8->7->3->5->6->7
8->4->3->2->1->4->10->9->8->7->6->5->3->7
8->4->3->5->6->7->3->2->1->4->10->9->8->7
8->4->3->5->6->7->8->9->10->4->1->2->3->7
8->4->3->7->6->5->3->2->1->4->10->9->8->7
8->4->3->7->8->9->10->4->1->2->3->5->6->7
8->4->10->9->8->7->3->2->1->4->3->5->6->7
8->4->10->9->8->7->3->4->1->2->3->5->6->7
8->4->10->9->8->7->6->5->3->2->1->4->3->7
8->4->10->9->8->7->6->5->3->4->1->2->3->7
8->7->3->2->1->4->8->9->10->4->3->5->6->7
8->7->3->2->1->4->10->9->8->4->3->5->6->7
8->7->3->4->8->9->10->4->1->2->3->5->6->7
8->7->3->4->10->9->8->4->1->2->3->5->6->7
8->7->6->5->3->2->1->4->8->9->10->4->3->7
8->7->6->5->3->2->1->4->10->9->8->4->3->7
8->7->6->5->3->4->8->9->10->4->1->2->3->7
8->7->6->5->3->4->10->9->8->4->1->2->3->7
8->9->10->4->1->2->3->4->8->7->3->5->6->7
8->9->10->4->1->2->3->4->8->7->6->5->3->7
8->9->10->4->1->2->3->5->6->7->3->4->8->7
8->9->10->4->1->2->3->5->6->7->8->4->3->7
8->9->10->4->1->2->3->7->6->5->3->4->8->7
8->9->10->4->1->2->3->7->8->4->3->5->6->7
8->9->10->4->3->2->1->4->8->7->3->5->6->7
8->9->10->4->3->2->1->4->8->7->6->5->3->7
8->9->10->4->3->5->6->7->3->2->1->4->8->7
8->9->10->4->3->5->6->7->8->4->1->2->3->7
8->9->10->4->3->7->6->5->3->2->1->4->8->7
8->9->10->4->3->7->8->4->1->2->3->5->6->7
8->9->10->4->8->7->3->2->1->4->3->5->6->7
8->9->10->4->8->7->3->4->1->2->3->5->6->7
8->9->10->4->8->7->6->5->3->2->1->4->3->7
8->9->10->4->8->7->6->5->3->4->1->2->3->7

总结

        首先深度搜索与回溯的代码结构是有规律的，1-是进行遍历所有的可能性（子节点），2-把访问过的数据进行标志（打标签），3-判断是否已经达到目标，达到则输出路径，否则递归进行下步，4-递归返回后回溯，恢复到递归前的状态。

        其次，回溯一般用来解决穷举的问题，可以看到递归函数内部都有一个for循环（n），再进行n-1次递归，因此其时间复杂度看似是O(n^(n-1))，实际上由于打标签（剪枝），会大大小于这个值