332.重新安排行程（二刷回看）

思路：

用回溯记录可能的行程，用vector<bool>used记录是否使用过,用如下代码判断是否放进path:

if(tickets[i][0]!=path.back())

                continue;

            if(used[i]==true)

                continue;

注意中止条件是

if(path.size()==(tickets.size()+1))

        {

            result.push_back(path);

            return;

        }

搜索所有路径会超时，应该找如何搜索时找最优解。

看代码后：

这道题目有几个难点：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环

2. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？

3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？

4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

这道题难是难在容器的选择和使用上。

第二问：

一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map 或者std::multimap 或者 std::multiset。

在遍历unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。

如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

相当于说不删就做一个标记！

函数返回值用的是bool！因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线.

代码如下：

unordered_map<string,map<string,int>> targets;

    bool backtracking(int ticketNum, vector<string> &result)

    {

        if(result.size()==ticketNum+1)

            return true;

        for(pair<const string, int> &target : targets[result[result.size()-1]])

        {

            if(target.second > 0)

            {

                result.push_back(target.first);

                target.second--;

                if(backtracking(ticketNum,result)) return true;

                result.pop_back();

                target.second++;

            }

        }

        return false;

    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {

        targets.clear();

        vector<string> result;

        for(const vector<string> & vec:tickets)

            targets[vec[0]][vec[1]]++;

        result.push_back("JFK");

        backtracking(tickets.size(),result);

        return result;

    }

51.N皇后（二刷回看）

思路：

无思路。

看视频：

画成树之后能发现问题变成了在每一行遍历回溯每个节点是否能放皇后。

定义参数：

vector<vector<string>> result;//存放结果

vector<string> chessboard(n, string(n,'.'));//初始化棋盘

void backtracking(int n, int row, vector<string> &chessboard)//n为棋盘边界，row为行，传入棋盘

终止条件：

if(row == n)

        {

            result.push_back(chessboard);

            return;

        }//到达叶子节点

单层逻辑：

for(int col=0;col<n;col++)

        {

            if(isValid(row,col,chessboard,n))

            {

                chessboard[row][col] = 'Q';

                backtracking(n,row+1, chessboard);

                chessboard[row][col] = '.';

            }

        }

是否符合条件的判断：

bool isValid(int row, int col, vector<string> &chessboard, int n)

    {

        for (int i = 0; i < row; i++) 

        {

            if(chessboard[i][col]== 'Q')

                return false;

        }// 同列的情况

        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)

        {

            if(chessboard[i][j]== 'Q')

                return false;

        }//45°的情况

        for(int i=row-1,j=col+1;i>=0 && j<n; i--,j++)

        {

            if(chessboard[i][j]=='Q')

                return false;

        }

        return true;

    }//135°的情况

37.解数独（二刷回看）

思路：

isValid函数中：判断横竖是否有相同元素，以及3*3中有没有相同元素。

回溯算法中：

中止条件为横竖都等于9，限制条件是如果元素不是'.'就跳过.但具体回溯不知道怎么写

看视频后：

递归函数的返回值需要是bool类型, 因为只需要找到一个符合的情况就返回

本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。

本题是二维递归：一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能。

bool backtracking(vector<vector<char>>& board)

    {

        for(int i=0;i<board.size();i++)

        {

            for(int j=0;j<board[0].size();j++)

            {

                if(board[i][j]!='.')

                    continue;

                for(char k='1'; k<='9';k++)

                {

                    if(isValid(i,j,k,board))

                    {

                        board[i][j]=k;

                        if(backtracking(board)) return true;

                        board[i][j]='.';

                    }

                }

                return false;

            }

        }

        return true;

    }

讨论是否合法：同行是否重复；同列是否重复；9宫格里是否重复

bool isValid(int row, int col, char val, vector<vector<char>> &board)

    {

        for(int i=0;i<9;i++)

        {

            if(board[row][i]==val)

                return false;

        }

        for(int j=0;j<9;j++)

        {

            if(board[j][col]==val)

                return false;

        }

        int startRow=(row/3)*3;

        int startCol=(col/3)*3;

        for(int i=startRow;i<startRow+3;i++)

        {

            for(int j=startCol;j<startCol+3;j++)

            {

                if(board[i][j]==val)

                    return false;

            }

        }

        return true;

    }

回溯总结：

回溯是递归的副产品，只要有递归就会有回溯，因此会和二叉树遍历和深度优先搜索结合。

回溯能解决如下问题：

组合问题：N个数里面按一定规则找出k个数的集合

排列问题：N个数按一定规则全排列，有几种排列方式

切割问题：一个字符串按一定规则有几种切割方式

子集问题：一个N个数的集合里有多少符合条件的子集

棋盘问题：N皇后，解数独等等

理解回溯应该使用树形结构！

回溯是用递归控制for循环嵌套的数量：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

回溯的优化方法只有剪枝！剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了。

回溯的模板：

void backtracking(参数) {

    if (终止条件) {

        存放结果;

        return;

    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {

        处理节点;

        backtracking(路径，选择列表); // 递归

        回溯，撤销处理结果

    }

}

组合问题：

注意startIndex的应用：如果是一个集合来求组合的话，就需要startIndex，如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex。

切割问题：

解决以下问题

1.切割问题其实类似组合问题

2.如何模拟那些切割线

3.切割问题中递归如何终止

4.在递归循环中如何截取子串

5.如何判断回文

巧用startIndex和i，注意切割过的地方不能重复切割所以递归函数需要传入i + 1。

子集问题：

在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

子集问题不需要加终止条件，因为本来就需要遍历整棵树。注意递增子序列这道题。

排列问题：

排列问题不需要startIndex,因为每层都是从0开始搜索而不是startIndex。需要used数组记录path里都放了哪些元素了。

去重问题：

注意树层去重和树枝去重，可以用used数组或者set去重，但set效率比较低。组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是同一树层上“使用过”。

例如：

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过

used[i - 1] == false，说明同一树层candidates[i - 1]使用过

棋盘问题（二刷重点）：

N皇后：棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度

解数独：使用二维递归，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

性能分析：

子集问题分析：

时间复杂度：O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n)

空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)

排列问题分析：

时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ..... 1 = n!。

空间复杂度：O(n)，和子集问题同理。

组合问题分析：

时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。

空间复杂度：O(n)，和子集问题同理。

N皇后问题分析：

时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * .... * 1。

空间复杂度：O(n)，和子集问题同理。

解数独问题分析：

时间复杂度：O(9^m) , m是'.'的数目。

空间复杂度：O(n^2)，递归的深度是n^2