代码随想录 回溯算法：回溯总结

回溯法理论基础

回溯法的本质是递归，可以想象成树理解。

回溯是递归的副产品，只要有递归就会有回溯

回溯法能解决什么问题

• 组合问题：N个数里面按一定规则找出k个数的集合
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等

回溯法模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合问题

名称	集合	组合元素数量	目标和	元素可否重复选取
组合	1-n个数（无重复数组）	k	/	不可
组合总和III	1-9个数（无重复数组）	k	n	不可
组合总和	无重复数组	/	target	可
组合总和II	有重复数组	/	target	不可

有重复数组需要树层去重，借助used数组。

有数量限制就加在终止条件；

有目标和就加一个sum，并加在终止条件；

元素如果可重读选取，startIndex进入递归时从i开始，表示当前元素可重复选；

电话号码的字母组合

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

每个集合中各挑选出一个数组，组成一个组合。各集合相互不影响；

多个无重复集合、组合元素数量给定、无目标和、不可重复选取。

切割问题

分割回文串

• 将切割问题抽象为组合问题
• 切割中递归如何终止？startIndex大于等于数组大小
• 如何截取字串？substr函数
• 如何判断回文？巧用动规减少循环次数

子集问题

子集问题是不限制个数的组合，所以在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

子集II 问题针对子集问题进行去重。在组合总和III 已经学会了树层去重，这道题也是一样的套路

递增子序列

子序列类似于子集，但是增加了递增的要求，另外原数组中有重复元素，这又要求我们去重。这就是与子集问题的两个区别。

排列问题

排列就是有序的集合。

排列问题的不同：

• 每层都是从0开始搜索而不是startIndex
• 需要used数组记录path里都放了哪些元素了

排列II

又增加了重复元素的条件，因此我们继续树层去重

去重本质

其实去重的本质是标记本层有哪些元素已经使用过了。所以使用set是一个很常见的想法。

但是因为题目一般数组元素的范围都比较小，使用数组来代替更能够节省时间。set的一些操作效率是比较低的，比如不断地哈希映射。

重新安排行程

这道题carl 使用了回溯的解法，后来提交就不通过了。

因为对于死胡同分支额外进行了一次遍历，导致大量无效重复的搜索。

进而使用Hierholzer算法。即深搜+后续遍历的思想，总是将死胡同先入栈。最后逆序输出。

棋盘问题

N皇后

棋盘问题其实更好理解。单层回溯搜索就是一行一行地放皇后，保证当前不与之前冲突的前提下放置。放好后进入递归放下一行。最终最后一行也放置完成了，就搜索到叶子节点，找到一套方案。终止。

解数独

N皇后是每行每列只有两种可能，放或不放。

数独是每行每列有9种可能。比前者深一层。