稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

回溯算法从入门到精通

回溯(Backtracking)是指在求解的过程中,不断的试探每一步的所有可能的解,如果发现不符合要求,就回退到最初的状态,尝试另外一种可能,直到所有的可能的解都找到。它与DFS的思想是一致的。

回溯通常用来解决的问题是,问题会分成很多步骤,每一步面临多个选择,有多种可能性,需要一个一个的尝试,最终需要找到所有的可能的解。回溯通常用递归来实现,并且它的时间复杂度一般都比较高。它基本上就是穷举和暴力搜索一样,但通过各种奇技淫巧可以做剪枝以降低复杂度。

最为经典的回溯算法问题就是迷宫问题,比如从一个格子a,出发,有二个方向,还不知道哪个是对的,那就分别向前走,一直走,直到撞墙了,或者到了死路了,才知道这个方向是错的;然后回退到a,按个方向继续走,这就是经典的回溯。

回溯的模板套路

运用回溯算法需要厘清四个条件:1)把问题每成多个步骤,一步一步的走完,就得到了一个解;2)每个步骤又分成多个备选选择,有些是符合要求的,有些则是不符合要求的;3)什么条件算是得到了解,或者说什么情况下算是把问题解决了,在这个条件时终止递归,并得到一个解;4)剪枝,如何剪掉不符合题意的选择或者步骤。

虽然说具体的问题的分析场景不太一样,也就是说具体的每个问题的分为子问题的方式,以及子问题的解决步骤还有回溯方式是不一样的,但整体来说,回溯算法是有套路的:

1
2
3
4
5
6
7
8
def backtracking(current_option):
   if satisfied:
     return solution
   if not satisfied:
     return null
   next_option = getNext()
   backtrack(next_option)
   undo next_option

下面来看一下一些典型的可以用回溯算法来求解的问题类型。

递归树

回溯是一个DFS的过程,是在遍历一颗递归树(State space tree),所以要想更好的应用回溯,最好画出一颗递归树,以更好的厘清回溯过程和剪枝。一个节点代表一个状态,一个路径代表一个操作,叶子节点表示递归到达终止条件。 比如说子集问题,给定一个无重复元素的数组,找出所有的子集,比如给定[1,2,3],那么递归树就会是这个样子的:

剪枝即是依据某些约束条件,把不符合要求的路径排除在外,这不单单排除一个节点,而是把这个节点的所在的路径都排除了,这个节点及其后面的DFS都不需要做了,就像把树的一根分杈剪掉一样,所以形象的称之为剪枝。

基础回溯问题

有一些非常典型的用回溯解决的问题,如子集(幂集),组合和排列问题,这些问题是基础的回溯算法应用问题,有标准的套路,用于理解回溯和训练加溯思维都是很好的例子。

子集(幂集)问题

子集是指一个如果 一个集合A的元素都属于另一个集合B,那么A就是B的一个子集,空集和全集也都是子集。回溯算法解决的问题,更准确的说是求一个给定集合(一般以数组形式给出)的幂集。一个集合所有子集所组成的集合,称之为该集合的幂集(Power set)。集合中每一个元素都有两种选择,加入某个子集,或者不加入,假如集合大小为n,那么一共会有2n个不同的子集,所以子集相关问题的复杂度,至少会是O(2n)的。

题目 题解 说明
78. 子集 题解 回溯模板,无需剪枝
90. 子集 II 题解 在78基础上进行剪 枝
1863. 找出所有子集的异或总和再求和 题解
2044. 统计按位或能得到最大值的子集数目 题解
题解


组合问题

题目 题解 说明
17. 电话号码的字母组合 题解
39. 组合总和 题解
40. 组合总和 II 题解
77. 组合 题解 子集的简化版本
216. 组合总和 III 题解
401. 二进制手表 题解 与216是同一题


排列问题

题目 题解 说明
46. 全排列 题解
47. 全排列 II 题解
784. 字母大小写全排列 题解
剑指 Offer 38. 字符串的排列 题解


高级回溯问题(搜索问题)

棋盘类问题

题目 题解 说明
37. 解数独 题解
51. N 皇后 题解
52. N皇后 II 题解


分割类问题

题目 题解 说明
93. 复原 IP 地址 题解 与131类似,但简单不少,因为只需要分四段即可
131. 分割回文串 题解 学会如何对字串分割子串
题解


构造类问题

题目 题解 说明
22. 括号生成 题解
题解
题解


DFS+回溯

题目 题解 说明
797. 所有可能的路径 题解 DFS+回溯
257. 二叉树的所有路径 题解
79. 单词搜索 题解
题解
题解
题解


其他枚举类问题

回溯本质上就是暴力穷举,所以一些枚举类问题也可以通过回溯来解决。

题目 题解 说明
816. 模糊坐标 题解 就是枚举,其实没用到回溯
1620. 网络信号最好的坐标 题解
149. 直线上最多的点数 题解
题解
题解


参考资料

Comments