回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯是递归的副产品，只要有递归就会有回溯。
回溯法简单来说就是按照深度优先的顺序，穷举所有可能性的算法，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。
回溯法的特点是深度优先遍历，也就是该问题的遍历顺序是1->2->3，然后从子节点3返回，从子节点2返回，再到1->3->2，以此类推。
状态的返回只有当前的节点不再满足问题的条件或者我们已经找到了问题的一个解时，才会返回，否则会以深度优先一直在解空间树内遍历下去。
所以根据这类问题，我们有一些优化剪枝策略以及启发式搜索策略。
所谓优化剪枝策略，就是判断当前的分支树是否符合问题的条件，如果当前分支树不符合条件，那么就不再遍历这个分支里的所有路径。
所谓启发式搜索策略指的是，给回溯法搜索子节点的顺序设定一个优先级，从该子节点往下遍历更有可能找到问题的解。
回溯法，一般可以解决如下几种问题：
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1,2}和{2,1}在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1,2}和{2,1}就是两个集合了。
记住组合无序，排列有序，就可以了。
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。
用回溯算法解决问题的一般步骤：
1、针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。
3、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
回溯函数伪代码如下：
回溯函数遍历过程伪代码如下：
for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){处理节点;backtracking(路径，选择列表);//递归回溯，撤销处理结果}for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
回溯算法模板框架如下：
voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){处理节点;backtracking(路径，选择列表);//递归回溯，撤销处理结果}}基本思想回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
示例:输入:n=4,k=2输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]直接的解法当然是使用for循环，例如示例中k为2，很容易想到用两个for循环，这样就可以输出和示例中一样的结果。
代码如下：
回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。
那么回溯法怎么暴力搜呢？
上面我们说了要解决n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。
递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。
此时递归的层数大家应该知道了，例如：n为100，k为50的情况下，就是递归50层。
那么我把组合问题抽象为如下树形结构：
可以看出这个棵树，一开始集合是1，2，3，4，从左向右取数，取过的数，不在重复取。
第一次取1，集合变为2，3，4，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2][1,3][1,4]，以此类推。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。
那么如何在这个树上遍历，然后收集到我们要的结果集呢？
图中每次搜索到了叶子节点，我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来，就可以求得n个数中k个数的组合集合。
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
函数里一定有两个参数，既然是集合n里面取k的数，那么n和k是两个int型的参数。
然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n]）。
为什么要有这个startIndex呢？
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。
其实不定义这两个全局遍历也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以我定义全局变量了。
所以需要startIndex来记录下一层递归，搜索的起始位置。
那么整体代码如下：
path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
如图红色部分：
此时用result二维数组，把path保存起来，并终止本层递归。
所以终止条件代码如下：
if(path.size()==k){result.push_back(path);return;}回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
如此我们才遍历完图中的这棵树。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
关键地方都讲完了，组合问题C++完整代码如下：
在遍历的过程中有如下代码：
这么说有点抽象，如图所示：
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。
注意代码中i，就是for循环里选择的起始位置。
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n=4，k=3，目前已经选取的元素为0（path.size为0），n-(k-0)+1即4-(3-0)+1=2。
从2开始搜索都是合理的，可以是组合[2,3,4]。
这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。
所以优化之后的for循环是：
说明：
示例1:输入:k=3,n=7输出:[[1,2,4]]
示例2:输入:k=3,n=9输出:[[1,2,6],[1,3,5],[2,3,4]]
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
本题k相当于了树的深度，9（因为整个集合就是9个数）就是树的宽度。
例如k=2，n=4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求k（个数）=2,n（和）=4的组合。
选取过程如图：
图中，可以看出，只有最后取到集合（1，3）和为4符合条件。
这里我依然定义path和result为全局变量。
至于为什么取名为path？从上面树形结构中，可以看出，结果其实就是一条根节点到叶子节点的路径。
所以代码如下：
还要强调一下，回溯法中递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数。
在上面已经说了，k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义。
所以如果path.size()和k相等了，就终止。
如果此时path里收集到的元素和（sum）和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。
所以终止代码如下：
if(path.size()==k){if(sum==targetSum)result.push_back(path);return;//如果path.size()==k但sum!=targetSum直接返回}如图：
处理过程就是path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。
如图：
已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。
那么剪枝的地方一定是在递归终止的地方剪，剪枝代码如下：
示例:输入："23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
从示例上来说，输入"23"，最直接的想法就是两层for循环遍历了吧，正好把组合的情况都输出了。
如果输入"233"呢，那么就三层for循环，如果"2333"呢，就四层for循环.......
理解本题后，要解决如下三个问题：
可以使用map或者定义一个二维数组，例如：stringletterMap[10]，来做映射，我这里定义一个二维数组，代码如下：
conststringletterMap[10]={"",//0"",//1"abc",//2"def",//3"ghi",//4"jkl",//5"mno",//6"pqrs",//7"tuv",//8"wxyz",//9};回溯法来解决n个for循环的问题例如：输入："23"，抽象为树形结构，如图所示：
图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出["ad","ae","af","bd","be","bf","cd","ce","cf"]。
回溯三部曲：
首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。
再来看参数，参数指定是有题目中给的stringdigits，然后还要有一个参数就是int型的index。
这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。
那么终止条件就是如果index等于输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。
然后收集结果，结束本层递归。
if(index==digits.size()){result.push_back(s);return;}首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。
然后for循环来处理这个字符集，代码如下：
注意：输入1*#按键等等异常情况
给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字可以无限制重复被选取。
示例1：输入：candidates=[2,3,6,7],target=7,所求解集为：[[7],[2,2,3]]
示例2：输入：candidates=[2,3,5],target=8,所求解集为：[[2,2,2,2],[2,3,3],[3,5]]
本题搜索的过程抽象成树形结构如下：
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！
这里依然是定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）
首先是题目中给出的参数，集合candidates,和目标值target。
此外我还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如何target==0就说明找到符合的结果了，但为了代码逻辑清晰，我依然用了sum。
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。
sum等于target的时候，需要收集结果，代码如下：
if(sum>target){return;}if(sum==target){result.push_back(path);return;}单层for循环依然是从startIndex开始，搜索candidates集合。
如何重复选取呢，看代码，注释部分：
以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum>target的话就返回。
其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。
对总集合排序之后，如果下一层的sum（就是本层的sum+candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
for循环剪枝代码如下：
给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。
说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
示例1:输入:candidates=[10,1,2,7,6,1,5],target=8,所求解集为:[[1,7],[1,2,5],[2,6],[1,1,6]]
示例2:输入:candidates=[2,5,2,1,2],target=5,所求解集为:[[1,2,2],[5]]
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！
所以要在搜索的过程中就去掉重复组合。
这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。这么一说好像很简单！
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过”是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates=[1,1,2],target=3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
选择过程树形结构如图所示：
这个集合去重的重任就是used来完成的。
if(sum>target){//这个条件其实可以省略return;}if(sum==target){result.push_back(path);return;}sum>target这个条件其实可以省略，因为和在递归单层遍历的时候，会有剪枝的操作，下面会介绍到。
前面我们提到：要去重的是“同一树层上的使用过”，如果判断同一树层上元素（相同的元素）是否使用过了呢。
如果candidates[i]==candidates[i-1]并且used[i-1]==false，就说明：前一个树枝，使用了candidates[i-1]，也就是说同一树层使用过candidates[i-1]。
此时for循环里就应该做continue的操作。
这块比较抽象，如图：
我在图中将used的变化用橘黄色标注上，可以看出在candidates[i]==candidates[i-1]相同的情况下：
那么单层搜索的逻辑代码如下：
回溯三部曲分析完了，整体C++代码如下：
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的分割方案。
示例:输入:"aab"输出:[["aa","b"],["a","a","b"]]
本题这涉及到两个关键问题：
这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
一些同学可能想不清楚回溯究竟是如何切割字符串呢？
我们来分析一下切割，其实切割问题类似组合问题。
例如对于字符串abcdef：
感受出来了不？
所以切割问题，也可以抽象为一棵树形结构，如图：
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。（这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。
那么在代码里什么是切割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。
可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。
那么判断回文的C++代码如下：
给定一个只包含数字的字符串，复原它并返回所有可能的IP地址格式。
有效的IP地址正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0），整数之间用'.'分隔。
例如："0.1.2.201"和"192.168.1.1"是有效的IP地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是无效的IP地址。
示例1：
示例2：
示例3：
示例4：
示例5：
提示：
切割问题可以抽象为树型结构，如图：
startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum，记录添加逗点的数量。
pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
然后验证一下第四段是否合法，如果合法就加入到结果集里
如果合法就在字符串后面加上符号.表示已经分割。
如果不合法就结束本层循环，如图中剪掉的分支：
然后就是递归和回溯的过程：
递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum要+1。
回溯的时候，就将刚刚加入的分隔符.删掉就可以了，pointNum也要-1。
主要考虑到如下三点：
给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:输入:nums=[1,2,3]输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2}和子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
有同学问了，什么时候for可以从0开始呢？
以示例中nums=[1,2,3]为例把求子集抽象为树型结构，如下：
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
全局变量数组path为子集收集元素，二维数组result存放子集组合。（也可以放到递归函数参数里）
递归函数参数在上面讲到了，需要startIndex。
从图中可以看出：
剩余集合为空的时候，就是叶子节点。
那么什么时候剩余集合为空呢？
就是startIndex已经大于数组的长度了，就终止了，因为没有元素可取了，代码如下:
if(startIndex>=nums.size()){return;}其实可以不需要加终止条件，因为startIndex>=nums.size()，本层for循环本来也结束了。
求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
那么单层递归逻辑代码如下：
给定一个可能包含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。
示例:
剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。
用示例中的[1,2,2]来举例，如图所示：（注意去重需要先对集合排序）
从图中可以看出，同一树层上重复取2就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！
C++代码如下：
如果要是全排列的话，每次要从0开始遍历，为了跳过已入栈的元素，需要使用used。
给定一个整型数组,你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
说明:
这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。
就是因为太像了，更要注意差别所在，要不就掉坑里了！
而本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了。
所以不能使用之前的去重逻辑！
本题给出的示例，还是一个有序数组[4,6,7,7]，这更容易误导大家按照排序的思路去做了。
为了有鲜明的对比，我用[4,7,6,7]这个数组来举例，抽象为树形结构如图：
本题求子序列，很明显一个元素不能重复使用，所以需要startIndex，调整下一层递归的起始位置。
但本题收集结果有所不同，题目要求递增子序列大小至少为2，所以代码如下：
在图中可以看出，同一父节点下的同层上使用过的元素就不能在使用了
那么单层搜索代码如下：
最后整体C++代码如下：
其实用数组来做哈希，效率就高了很多。
注意题目中说了，数值范围[-100,100]，所以完全可以用数组来做哈希。
那么优化后的代码如下：
给定一个没有重复数字的序列，返回其所有可能的全排列。
我以[1,2,3]为例，抽象成树形结构如下：
首先排列是有序的，也就是说[1,2]和[2,1]是两个集合，这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
可以看出叶子节点，就是收割结果的地方。
那么什么时候，算是到达叶子节点呢？
当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。
而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
整体C++代码如下：
给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。
这里又涉及到去重了。
那么排列问题其实也是一样的套路。
还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
我以示例中的[1,1,2]为例（为了方便举例，已经排序）抽象为一棵树，去重过程如图：
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
我就用输入:[1,1,1]来举一个例子。
树层上去重(used[i-1]==false)，的树形结构如下：
树枝上去重（used[i-1]==true）的树型结构如下：
大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。
给定一个机票的字符串二维数组[from,to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从JFK开始。
直觉上来看这道题和回溯法没有什么关系，更像是图论中的深度优先搜索。
实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。
这道题目有几个难点：
对于死循环，我来举一个有重复机场的例子：
为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。
有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢？
一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map或者std::multimap或者std::multiset。
含义如下：
再说一下为什么一定要增删元素呢，正如开篇我给出的图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。
如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。
相当于说我不删，我就做一个标记！
本题以输入：[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]为例，抽象为树形结构如下：
当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。
参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。
我们之前讲解回溯算法的时候，一般函数返回值都是void，这次为什么是bool呢？
因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：
拿题目中的示例为例，输入:[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。
所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。
if(result.size()==ticketNum+1){returntrue;}123\
回溯的过程中，如何遍历一个机场所对应的所有机场呢？
可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。
遍历过程如下：
分析完毕，此时完整C++代码如下：
如果不加const，也可以复制一份pair，例如这么写：
n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数n，返回所有不同的n皇后问题的解决方案。
每一种解法包含一个不同的n皇后问题的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。
首先来看一下皇后们的约束条件：
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
下面我用一个3*3的棋盘，将搜索过程抽象为一棵树，如图：
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。
我依然是定义全局变量二维数组result来记录最终结果。
参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。
可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。
if(row==n){result.push_back(chessboard);return;}递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？
因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
那么按照这个模板不难写出如下C++代码：
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：数字1-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用'.'表示。
一个数独。
答案被标成红色。
棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。
怎么做二维递归呢？
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，我抽取一部分，如图所示：
递归函数的返回值需要是bool类型，为什么呢？
不用终止条件会不会死循环？
递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！
那么有没有永远填不满的情况呢？
这个问题我在递归单层搜索逻辑里在来讲！
在树形图中可以看出我们需要的是一个二维的递归（也就是两个for循环嵌套着递归）
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
代码如下：（详细看注释）
注意这里returnfalse的地方，这里放returnfalse是有讲究的。
因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
那么会直接返回，这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！