目录

• 回溯思想

• 回溯算法能解决的问题

• 回溯算法三部曲

• 组合问题（注意剪枝）

  • 特点

    • 什么时候需要startIndex？

  • 普通组合

  • 组合求和

    • （一）
    • （二）
    • （三）
    • 组合问题如何去重？

  • 多集合的组合问题

• 切割问题

• 子集问题

  • 特点
  • 子集问题的去重
  • 递增子序列（不能排序时如何去重？）

• 排列问题

  • 排列问题的去重

• 。。。

• 重新安排行程

• n皇后

• 解数独

回溯思想

for循环横向遍历，递归纵向遍历，回溯不断调整结果集

比较适合数组长度小或字符串长度小的情况，太大了会超时，考虑动态规划T516

回溯算法能解决的问题

回溯算法三部曲

注意： 进入递归函数前做过什么操作，调用递归函数后就要撤销什么操作

组合问题（注意剪枝）

特点

• 固定了每种组合的大小(k)，对应于树中，就是只取叶子结点，对应的终止条件为：
• 可优化（剪枝）
• 考虑startIndex：因为[1,2]和[2,1]是一种组合方式，只取一个，所以每次遍历要限制一个起点位置（如1），只要它往后的元素（如2），这样就不会出现刚才这种情况 但也要注意分情况：

什么时候需要startIndex？

如果是一个集合来求组合的话，就需要startIndex

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex

普通组合

剪枝方法： for循环在寻找起点的时候要有一个范围，如果这个起点（代码中的i）到集合终止n之间的元素已经不够题目要求的k个元素了，就没有必要搜索了。(注意这里不涉及到数组，是直接添加i,而不是add(nums[i]),所以最后一个数是n而不是看数组下标n-1)。

现已经找了path.size()个元素，还需k-path.size()个，那么至少要保证n-i+1>=k-path.size()，即：

组合求和

特点： 关注的是元素和，所以单循环操作中要加上sum+=i，当然也要撤销。且元素和sum要作为终止条件，所以回溯函数的形参中要加上int sum和int target。

剪枝方法： 除去普通组合中的剪枝外(1)，还要考虑当已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接剪掉(2)

（一）

leetcode.216，找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

（二）

leetcode.39，给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

注意： 和（一）的区别就是调递归函数时，startIndex不再是i+1了，而是i，因为可重复取，所以i这个元素下一次还可以继续取；此外，还没有要求k个，所以for的终止条件也要改变

（三）

leetcode.40

组合问题如何去重？

把所有组合求出来，再用set或者map去重，这么做很容易超时！所以要在搜索的过程中就去掉重复组合。

区分： “树枝去重” vs “树层去重” 例：如原集合{1，1，2，3}，若[1,1,2]这样的子集形式不合要求，那么就需要树枝去重；若[1(第一个1),2,3]，[1(第二个1),2,3]不能同时存在，那么就需要树层去重

用bool型数组used来反映每个元素是否被用过

首先对给定数组排序，让相同的元素挨在一起

解释：

i>0，因为i=0时，i-1越界，且i=0它是同层遍历的第一个元素，它前面没有元素

多集合的组合问题

leetcode.17

每一个数字即对应一组字母集合，此时不需要startIndex，因为对每一个集合都要从头遍历，只需要一个num指示遍历到第几位数字了，所以终止条件为num==digits.length()

切割问题

本质也是组合问题（在i位置分割，求i的组合），要根据切割要求单独写个方法（如是否是回文等）

终止条件：

截取操作：

substr(首位置，末位置+1)，+1是因为该函数是左闭右开的

注意： 切割过的地方不能重复切割，所以递归函数需要传入i + 1；只有一个集合的组合问题，所以需要startIndex

子集问题

特点

• 在树形结构中，子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。
• 找子集，显然原数组中元素不能重复使用

终止条件：

子集问题的去重

和组合问题的去重方法一样

递增子序列（不能排序时如何去重？）

注意： 不能对原数组进行排序，所以要摒弃之前的去重方法

递归后，used[]不能撤销，因为used[]是在回溯方法中new的，一次完整for循环就是遍历一层，每层for循环完了之后，used[]会清零的，如果每个枝桠遍历完，就撤销了，那在继续for的过程中，就不知道同层有重复元素

每一层都会有一个专门的used[]数组，可以理解为used1[]、used2[]。。（内存位置不同），每个枝桠遍历完了，退回到结点处时，used会恢复成该层的used[] (其实它就在原内存处)；这题因为没法排序，所以不得不每次调回溯方法时都new一个数组，造成空间浪费。之前可以排序的情况就可以把数组设为全局变量，公用一个数组，加上撤回操作完成，看值相同的相邻元素是否在同一层。也可这样new多次，不撤回，本质一样。

leetcode.491

排列问题

特点：

1. [1,2,3]和[2,1,3]算两种，不需要starIndex，因为取了2之后，还是要从1开始遍历选取，即for(int i=0;i<arr.length;i++)，但注意要跳过此时已经选择的2，即用used[]来标记2选过了，if(used[i])?continue
2. 取叶子结点，终止条件为 当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

排列问题的去重

和组合问题的去重方法一样

注意：

used[i-1] == false也可以（更好），used[i-1] == true也可以！

使用set去重比使用used[]去重，时间复杂度和空间复杂度都更高

。。。

重新安排行程

n皇后

解数独