一、基本概念1、何谓回溯法？ 也叫回溯检索法，说白了就是检索方式。
其实回溯是递归的副产物，有递归就有回溯。
回溯函数也称为递归函数。
2、追溯法的高效追溯法的本质是包罗万象的，所以效率不高
虽然一些修剪树枝的操作可以稍微提高效率，但是仍然是低效率的算法
3、溯因法解决的问题常用于解决以下五类问题：
* 1)组合问题(不强调**要素的顺序，从n个中按照一定的规则找到k个的集合)2)排列问题) **强调要素的顺序，把n个的个数按照一定的规则全部排列， 求有多少排列方法)3)切分问题)一个字符串按照一定的规则有几种切分方法)4)子集问题)一个n个集合中有几种切分方法4、回溯法所有回溯法都能解决的问题
由于递归法解决了在集合中递归寻找子集，集合的大小构成树的宽度，递归的深度构成树的深度。
递归需要结束条件，所以必然会变成高度有限的n叉树。
5、回溯跟踪(参数if )退出条件)保存结果； 返回； (for )选择：基本层集合中的要素)处理树中的节点、孩子的数量为集合的大小)节点； 后退跟踪(路径、选择列表)； //递归，即追溯到下一个层次，还原处理结果}}函数模板返回值和参数
名称通常表示为后退跟踪返回值。 一般来说，void参数并不像二叉树一样可以一次基本确定。 因此，一般先写逻辑，然后在需要什么参数时填写什么参数的回溯函数的结束条件
从树中可以看出何时达到了结束条件，一般情况下找到了叶节点，即找到满足条件的一个答案，保存该答案，结束本层递归
保存if (结束条件)结果； 返回； )向后搜索遍历过程
回溯：在集合中递归探索。 集合的大小构成树的宽度，递归的深度构成树的深度
for (选择：处理该分层集合中的元素(树中的节点的孩子的数量为集合的大小) )节点； 后退跟踪(路径、选择列表)； //递归回溯，撤销处理结果}图中，集合大小和孩子数量相等的for循环穿越集合区间，可以理解一个节点上有多少个孩子，该for循环将执行多少次。 backtracking在这里自己调用自己，实现递归。 for循环可以理解为遍历。 “递归”是纵断面遍历。 这样可以完全遍历此树。 一般来说，搜索叶节点是搜索的结果之一。 6、剪枝：不要想得太复杂。 实际上，啊~可以修剪的地方是递归中各层的for循环中选择的开始位置，所以如果在for循环中选择的开始位置之后的元素个数不足所需的元素个数，就不需要检索了。 也就是说，请控制for循环的扫描结束条件
*已选择的元素个数**path.size(***其他所需元素个数**k - path.size ) ) ***在集合n中，从**n-(k-path.size ) **的位置开始I(*7)、问题的感想在for循环中，必须心里明白是横向、递归、纵向。
把握
回溯函数的参数决定了你代码的复杂性。 如果参数设置合理，就可以简化整个程序
例如，在字母数字组合的情况下，这个问题的下标有两个，一个是字母字符串的下标，一个是输入的数字字符串的下标，如何有机地结合是值得考虑的问题
8、时间复杂度主要分为几个题型进行归纳
n 表示数组的大小
组合问题的时间复杂度为o(2^n ) :一个二叉树，每个节点有两个孩子(一个向下递归，一个向右for循环)，所以时间复杂度为数组问题的时间复杂度为o(n！ ()这里的for每层从第一个要素开始，但是递归向下的时候不重复已经使用过的要素，所以时间的复杂度是o(n )！ (二)问题第三十九题第四十题的组合问题40和39的区别主要有两点。
在1，40个问题中，给定数据集上的每个数字组合只能使用一次，但39个问题可以重用
2、在40个问题中给定的数据集的元素本身可能是重复的，但39个问题不是重复的
首先想到的是求出所有的组合，用set或map去除重量，但这样容易超时，所以最好在搜索中去除重复的组合。
这里的重复其实有两个层面的理解。 一个是在同一个树枝上重复，另一个是在同一个树层上重复。
第40题是，允许同一枝重复，但不允许同一树层重复的结构，
去除重量的概念有两种，去除树枝的重量和
树层的去重 第131题 分割回文串这里：
横向表示在不同的位置切
纵向表示切几刀，每往下一层就表示多切一刀
终止就是切到了最后一个元素后面
本题是挺难的呢~
难点一：切割问题如何抽象为组合问题难点二：如何模拟那些切割线（组合直接放进path，但切割需要通过下标，来对字符串进行分割）难点三：切割问题中的递归如何终止，是要靠传入的 startIndex下标来完成对终止条件的判断难点四：在递归中如何截取子串，通过下标难点五：如何判断回文串，双指针法，一个从前往后，一个从后往前，判断指向的元素是否相等 // 截取的过程，真的没有想到哇~边截取，边判断是否为回文串 if(isPalindrome(s, startIndex, i)) { // 获取区间内的子串是回文串,则截取这段子串放进 path 中 string str = s.substr(startIndex, i - startIndex + 1); path.push_back(str); }debug 报错超时的查错思路：
1、一般大规模用例的话，那就是代码写的不够精简，用时比较就
2、一般小规模用例的话，那一定就是代码有bug，一般在while循环中找错误，这种通常在while循环中会犯错
3、如果是有递归太深的话，会报错 stack overflow 栈溢出
第46题 全排列处理排列问题是需要一个 used 数组，就不需要 startIndex ，这个used数组是用来记录是否用过这个元素
取的是叶子节点。
第47题 全排列V2 used[i-1] == true 说明同一树枝 nums[i-1] 使用过used[i-1] == false 说明同一树层 nums[i-1] 使用过如果同一树层 nums[i-1] 使用过，则直接跳过这里used[i-1] == true 或者used[i-1] == false 都是可以通过的对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索used[i-1] == false 树层去重的树形结构
used[i-1] == true 树枝去重的树形结构
第332题 重新安排行程题解思路：
1、有点类似于 图论中的深度优先搜索 dfs
2、的确是有用到深搜，在查找路径的时候，也有用到回溯，因为找路径嘛，不回溯怎么找路径呢？
其实深搜一般也都是用回溯法的思路。
难点：
1、一个行程中，如果航班处理不好，有可能成为一个圈，变成死循环 (一张机票不是只能用一张嘛，用完一张弃之应该就可以了吧)
2、要求按字母排序 取得最终的结果，思考该怎么记录映射关系呢 (母鸡哦~)
答：按字母排序，就可以用 std::map 或者std::set 或者 std::multimap
3、使用回溯法，那么终止条件是什么呢？ (每张机票都使用一遍吗？)
4、搜索的过程中，如何遍历一个机场所对应的所有机场呢？ (也是母鸡的)
答：一个机场映射多个机场，可以用 map ，注意 std::unordered_map 效率相对是高的
剖析：
1、这道题是第一次用 关联容器 嵌套一个 关联容器 ，可以有两种选择，
// 但是这个有一个缺点，当使用set容器来存储时，一旦删除其中的元素，迭代器就会失效。。。为什么要删除呢？因为用过的机票不删除的话，可能会出现死循环unordered_map<string, multiset<string>> targets// 含义：：unordered_map<出发机场，到达机场的集合>// 使用map来存储多个机场的集合，用 “航班次数” int值 来标记是否使用过这个机场，就无需对集合做删除或者增加元素的操作unordered_map<string, map<string, int>> targets// 含义：：unordered_map<出发机场， 航班次数>2、通常说回溯函数的返回值类型都是 void ，这道题把递归函数设定为 bool ，
因为只需要找到一条符合条件的行程即可返回，无需遍历全部，所以找到一个符合题意的，也就是一个到达叶子节点的树枝，就控制函数 return
3、终止条件分析
机场个数 等于 机票个数+1，就说明找到了一个行程，把整条航班串起来了。
4、单层递归逻辑
可以说本题是需要找到一个数据进行排序的容器，而且还要容易增删元素，且迭代器还不能失效
5、这道题真的不简单哦~
其实，感觉，很大程度上，难是因为对容器的操作并不是很熟练，看到这种容器的嵌套，就觉得恐惧，但是~~不要怂！冲冲冲！！！~ 先看会，再写对！
map容器嵌套一个map容器的用法，很妙，但是很难想得到，可太难了~
不过理解了一个点，其实一个关联容器，也就是哈希映射，就把它理解为数组，对于set容器也是一样的理解，
数组的下标就是 key，数组中存放的元素就是 value
map 的 key 根据选择的容器类型不同，可以是有序或者无序，map 的 value 就是对应着 key 的一个元素
set 的 key 根据选择的容器类型不同，可以是有序或者无序，
这里再复习一下
第51题 棋盘问题–N皇后N皇后问题是回溯算法解决的经典问题，同上一题相似，又是用到二维矩阵。
首先，先理清 皇后们 的约束条件：
1、不能同行
2、不能同列
3、不能同斜线
把整个棋盘初始化为一个 N * N 的点点组成的矩阵，找到合法位置就将其覆盖为 Q 代表把皇后放置在那里
// 这里的初始化属于打死我也想不到的，一个一维的 vector 容器，硬生生初始化为一个二维方阵，很妙，但是我想不到哇vector<string> chessboard = (n, string(n, '.')) 第37题 解数独 数独的规则：
1、定数独 永远是 9*9 的形式
2、给定的数独序列只包含数字 1-9 和 ’ . ’ （ ’ . '表示空白格 ）
3、可以假设给定的数独只有唯一解
4、游戏规则： 同行同列不可重复，且每一个以粗实线分隔的3*3的宫内只能出现一次，
数独问题 需要用 二维递归 的回溯暴力搜索，之前做的题目都是一维递归，包括N皇后，因为N皇后虽然是一个矩阵，但是它每一行每一列只放一个皇后，
只需要一层 for 循环遍历一行，递归来遍历列，然后一行一列来确定皇后的唯一位置。
数独的棋盘中，每一个位置都要放置一个数字，并且检查数字是否合法，解数独的树形结构要比N皇后的更宽更深。
回溯三部曲：
1、递归函数以及参数 递归函数的返回值需要是 bool 类型，因为解数独找到一个符合的条件就可以立即返回，相当于找到从根节点到叶子节点的一条路径。 2、递归终止条件 无需终止条件，因为解数独需要遍历整个树形结构，寻找可能的叶子节点，就立即返回。分析一下，没有终止条件，要么就是不符合条件继续往下或者往右搜索，要么就是填满了整个棋盘，这时候就表明正好是符合我们的预期，就是我们要的结果咯~ 3、递归单层搜索逻辑