回溯算法总结
回溯算法总结
一、回溯模板回顾
void backTracking() {
if(终止条件）{
收集节点
return;
}
for(广度遍历) {
处理节点
backTracking();
回溯(和处理节点正好相反)
}
return;
}二、回溯可以解决的问题
模板总结
限定组合的元素数量/限定组合的相加和——>if终止条件
数组中无重复元素，组合不能重复且每个元素只能使用一次——>从startIndex（每次递归时是自身下一个元素）开始，到末尾结束
数组中无重复元素，组合不能重复且每个元素可以使用多次——>startIndex每次从自身开始，到末尾结束
数组中有重复元素，组合不能重复且每个元素只能使用一次——>排序，used数组限定树层去重，树枝不去重
排列问题——>不能设置startIndex数组，方案1：每次访问元素的时候在path中寻找，看看是否有这个元素，有则不访问；方案2：设置used数组，深度递归时，如果used为true，那么说明该元素访问过，跳过
1.组合问题
77组合
限定了组合的元素数量，组合不能重复，每个元素只能用一次。
if终止条件为组合长度为k；for循环条件为了保证组合不出现重复，应该从startIndex开始，到n结束；for中为向path中添加元素、递归、回溯。
216组合总和III
限定组合元素数量和相加和，组合不能重复，组合中每个元素只能用一次
if终止条件为组合长度为k且相加和为n；for循环条件为了保证组合不能重复且每个元素只能用一次，从startIndex开始，到9结束；for中为向path添加元素、递归、回溯
39组合总和
无重复元素，限定组合元素的相加和，组合不能重复，组合中每个元素可以使用多次
if终止条件为相加和为target；for循环条件因为每个元素可以使用多次，且组合不能重复，所以也没必要从0开始，直接每层循环从startIndex开始即可，不过上面几道题目startIndex是每次都是本元素的下一个元素，保证每个元素只能使用一次，本题目只需要每次startIndex都从本元素开始即可，这样一个元素就可以使用多次，且不会和前面的组合重复；for循环体向path中添加元素、递归、回溯。
40组合总和II
有重复元素（示例中有），限定元素相加和，组合不能重复，组合中每个元素只能使用一次
if终止条件为相加和为target；先对数组进行排序，这样才能使用used数组，for循环条件因为每个元素只能使用一次且组合不能重复，所以设置startIndex，每次startIndex从自身的下一个元素开始，组合又不能重复，所以得设置used数组，限定树层重复元素就跳过，树枝重复元素允许继续，used初始化为false，深度递归也就是for循环体内递归的时候，将该数字的used设置为true，允许继续访问。
17电话号码的字母组合
这道题目涉及到了具体的情境，和上面几道题不太一样。限定组合元素长度，每个元素可以使用多次。
if终止条件为长度和数字长度相等，每次取元素都和上次无关，所以for循环条件从startIndex开始，到该数字代表的字母末尾结束。
2.切割问题
切割问题的关键在于如何模拟切割线，找到子串。可以用startIndex来模拟切割线，startIndex所指向的元素的后面那个空，实际上就是切割线。切割一次，然后在后面继续切割即可，每次只需要继续切割，然后进行判断，如果是回文串，那么就将这个子串加入到集合中。
切割问题相比组合问题，要注意的点少很多。
131分割回文串
if终止条件为已经切割到了末尾，也就是startIndex已经指向了最后一个元素。for循环遍历条件，因为每次切割都需要从上次切割的后面来进行切割，所以需要设置startIndex，每次指向它的下一个元素；for循环体，判断新切割的子串是否是回文串、递归、回溯。
93复原IP地址
实质上也是切割子串，对每个子串的要求是不能有别的字符，在0-255之间。
if终止条件，分割三次即为结束；for循环遍历条件仍然是需要设置startIndex，从本元素的下一个元素开始分割，判断此次分割的子串是否是合法的ip地址；for循环处理条件，如果是合法的ip地址，那么就加入一个点，并且继续分割。
3.子集问题
子集问题的关键点在于：收集的是路径上的所有节点，而不单单是叶子节点。所以if中收集了一个节点不能写return。
78子集
没有重复元素，子集不能重复，每个元素只能使用一次
if终止条件，因为收集的是路径上的所有节点，所以不需要进行判断，直接将所有节点全部收集，收集到数组末尾就结束，此时startIndex=nums.size()。for循环条件，每个元素只能使用一次，所以需要设置startIndex。
90子集II
有重复元素，子集不能重复，每个元素只能使用一次。
if终止条件收集到数组末尾就结束，此时startIndex=nums.size()。有重复元素，需要先将数组排序。for循环条件，每个元素只能使用一次，需要设置startIndex；for循环处理，树层去重，树枝不去重，设置used。
491非递减子序列
有重复元素，序列中至少有两个元素，子序列不重复，每个元素使用一次
if终止条件，如果序列长度大于等于2，那么就将其加入结果数组中。for循环条件，每个元素使用一次，需要设置startIndex；for循环处理，递增则加入，树层去重，树枝不去重，设置used或者设置uset记录广度中是否使用过该元素。
4.排列问题
46全排列
不含重复数字，限定排列长度，排列不能重复，每个元素只能使用一次。
if终止条件为长度达到了数组长度；for循环条件为每次从0开始，但是要判断这个元素是否已经访问过，如果访问过了，跳过本次广度遍历；for循环体将元素加入path、递归、回溯。
47全排列II
包含重复数字，限定排列长度，排列不能重复，每个元素只能使用一次。
if终止条件为长度达到了数组长度；因为排列不能重复，但是又有重复元素，所以需要将数组先排序， 排列类的题目不能设置startIndex，否则访问不了全部的数组元素，
然后利用used数组，一方面是重复元素进行树层去重，同时树枝遇到了重复元素可以继续访问；另一方面是为了检测本元素是否使用过，如果使用过，那么在深度递归的时候，该元素的used值应当就是true，此时也跳过本次访问；for循环体中为将元素加入path、递归、回溯。