回溯算法的心得
回溯算法的本质是穷举，是利用递归进行穷举，一般来首，我们常见的穷举方式就是for循环遍历，是遍历访问每一个值。但是这种情况应该是你知道可以套几层循环的情况。
而使用回溯算法是：你都不知道要循环多少层，都不知道在哪里终止，需要循环的条件一变化就没办法，此时那就是回溯算法最管用了
回溯算法是递归的副产物，有递归肯定需要回溯
利用回溯算法可以解答的题目都是可以抽象成树形结构（N叉树）。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度
回溯算法的模板：
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
回溯算法适合的问题
组合问题
77.组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案
一个元素不重复的集合，组合，元素不可以被重复选取
每递归一层，集合中的下标向后移动一位，防止出现相同结果
216.组合总和|||
与77.组合相似，只不过是将得到的组合中的数相加起来了
一个元素不重复的集合，组合相加，元素不可以被重复选取
每递归一层，集合中的下标向后移动一位，防止出现相同结果
难点：剪枝操作：至多可以遍历到什么位置上 9 - (k - nums.size()) + 1
17.电话号码的字母组合
多个集合(元素不重复)的组合
难点：对数字和字母的关系映射
39.组合总和
一个元素不重复的集合，组合相加，元素可以被重复选取
因为元素可以被重复选取，每递归一层，集合中的下标不用移动
难点：剪枝操作：需要先对数组中的元素进行排序，然后如果 sum + candidates[i] > target 就终止遍历
40.组合总和||
一个元素有重复的集合，组合相加，元素可以被重复选取
因为元素可以被重复选取，每递归一层，集合中的下标不用移动，但是需要去重
难点：去重操作
只有排序之后才可以进行剪枝操作和去重操作
剪枝操作和39.组合总数相同
去重操作需要使用used[]数组进行树层去重操作
切割问题
131.分割回文串
需要的前置知识：判断字符串是否是回文串
一个元素有重复的字符串，从第一个元素开始往后，每层添加一位进行分割
因为字符串要被不断分割，每递归一层，字符串的下标向后移动一位
难点：递归分割字符串
先判断是否满足回文串
再进行递归回溯
93.复原IP地址
很多公司面试的题目
需要的前置知识：判断截取数字的合法性
与分割回文串相似，都是分割完成之后进行判断
使用pointNum记录所添加的逗点，在满足三个逗点之后，在收集结果前判断最后一个都逗点后面的数字是否合法
难点：递归/回溯字符串
先判断是否合法
添加逗点，逗点数增加
递归的时候注意下标的移动是+2
回溯的时候回复字符串和逗点数减少
子集问题
78.子集
收集树形结构的所有节点
一个无重复元素的集合，元素不可以被重复选取
每递归一层，集合中的下标向后移动一位，防止出现相同结果
比较简单
90.子集||
收集树形结构的所有节点
一个有重复元素的集合，元素不可以被重复选取
因为有相同的元素，会造成重复情况，所以需要进行去重
难点：去重操作
使用used数组进行树层去重
排序问题
46.全排列
树枝去重
一个无重复元素的集合，只需要考虑树枝去重就可以
可以直接使用path容器去重
可以使用used[]数组进行去重
47.全排列||
树枝去重+树层去重
一个有重复元素的集合，需要考虑树枝去重和树层去重
使用used[]数组进行去重
难点：used[]数组对树层和树枝不同的去重操作
棋盘问题
51.N皇后
二维数组表示棋盘
需要的前置知识：判断棋盘上位置的合法性
难点：对棋盘的抽象
37.解数独
二维数组表示棋盘
需要的前置知识：判断棋盘上数字的合法性
不仅需要遍历棋盘的每一格，还需要遍历每一格上的不同数字
难点：二维递归
其他问题
491.递增子序列（和子集问题比较像）
不能排序，排序会打乱集合中的递增顺序
使用set去重，因为set是不可重复的
set不回溯，收集的是当前层的所有出现过的元素
332.重新安排行程
难点：行程的映射
难点：数据结构的选取
难点：终止条件
