定义
回溯法 采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
- 找到一个可能存在的正确的答案;
- 在尝试了所有可能的分步方法后宣告该问题没有答案。
一般来说,回溯算法用于 搜索一个问题的所有的解,通过深度优先遍历的思想实现。
下图是经典全排列问题的回溯算法图解,当你写回溯算法遇到问题,或者说不确定如何进行剪枝时,画出这样的图会有很大的帮助。
常见问题种类
排列、组合、子集相关问题
39. 组数总和
40. 组数总和2
46. 全排列
47. 全排列2
思考可以剪枝的条件, 为什么有的时候用 used 数组,有的时候设置搜索起点 begin 变量,理解状态变量设计的想法。
Flood Fill
Flood 是「洪水」的意思,Flood Fill 直译是「泛洪填充」的意思,体现了洪水能够从一点开始,迅速填满当前位置附近的地势低的区域。类似的应用还有:PS 软件中的「点一下把这一片区域的颜色都替换掉」,扫雷游戏「点一下打开一大片没有雷的区域」。
字符串中的回溯问题
字符串的问题的特殊之处在于,字符串的拼接生成新对象,因此在这一类问题上没有显示「回溯」的过程,但是如果使用 StringBuilder 拼接字符串就另当别论。