回溯算法作为一种经典的有效的暴力搜索策略。其基本思想是搜索过程中沿着一条路径一直往前走,当探索到某一步时发现无法满足要求时,则退回到上一步选择另外一条路径继续往前搜索。对于许多大规模复杂问题而言,很多时候都可以通过回溯算法尝试解决
算法模板
结合LeetCode刷题经验,现对回溯算法的解题思路进行总结,并形成下面的伪代码模板。我们首先需要两个全局变量:result、state。前者用于保存最终搜索结果;后者用于记录搜索过程中的状态信息。故在程序入口getResult方法中首先需要通过init方法完成全局变量的初始化,最后直接返回全局变量result作为题解即可。而这期间通过search方法进行回溯搜索即可
search方法的最重要思路是根据当前状态等信息获取下一步搜索的可选择空间,即通过调用getAvailableList方法实现,然后遍历该可选择空间。具体地对于每个选择,先判断是否符合条件。如果符合,则说明可以选择它继续往前搜索。那么我们第1步先做出选择,包括对状态变量state的更新;第2步通过递归调用search方法实现所谓的一直往前搜索;第3步当递归调用结束返回时则说明已经当前搜索路径已经退回到上一步了,这个时候我们就需要撤销第1步做出的选择对状态变量的影响了。总而言之,回溯的关键就在于在递归搜索之前需要做出选择,而在递归搜索之后需要撤销选择
前面提到search方法会一直递归调用下去。那递归终止条件是什么呢?其实也很简单,第一种是发现不满足合法条件时直接return,即所谓的剪枝优化;第二种则是搜索成功,此时需要根据状态等信息将当前的搜索结果添加最终结果当中去
1 | /** |
实践
LeetCode: 17. 电话号码的字母组合
这里以 LeetCode 第17题 <电话号码的字母组合> 为具体示例来进行阐述
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。数字到字母的映射如下图(与电话按键相同),注意1不对应任何字母
示例 1:
输入:digits = “23”
输出:[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]示例 2:
输入:digits = “”
输出:[]示例 3:
输入:digits = “2”
输出:[“a”,”b”,”c”]
按照模板则解法如下所示。由于本题在搜索过程中,任意一个搜索都是合法的,故不需要判断每次选择的合法性,直接按照 “做出选择-递归搜索下一个-撤销选择” 的思路进行处理即可
1 | /** |
LeetCode: 51. N皇后
这里以 LeetCode 第51题
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位
示例 1:
输入:n = 4
输出:[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释:如下图所示,4皇后问题存在两个不同的解法
示例 2:
输入:n = 1
输出:[[“Q”]]
按照模板则解法如下所示。本题中对于皇后的放置位置有一定要求,棋盘中的行、列、斜线不同同时放置两个皇后,故在遍历时通过isValid方法保证当前选择的合法
1 | public static class Solution { |
剑指Offer(第2版): 12. 矩阵中的路径
这里以 LeetCode 的剑指Offer(第2版)题单中的第12题 <矩阵中的路径> 为具体示例来进行阐述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
示例 1:
输入:board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出:true示例 2:
输入:board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
输出:false
按照模板则解法如下所示。一方面本题每次的搜索路径为上、下、左、右这四个方向上未使用过的网络;另一方面本题只需判断能够搜索成功即可。所以当第一次搜索成功后,即可以不再进行搜索。故解法中加入了基于exist结果判断的剪枝优化
1 | /** |
剑指Offer(第2版): 13. 机器人的运动范围
这里以 LeetCode 的剑指Offer(第2版)题单中的第13题 <机器人的运动范围> 为具体示例来进行阐述
地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?
示例 1:
输入:m = 2, n = 3, k = 1
输出:3示例 2:
输入:m = 3, n = 1, k = 0
输出:1
按照模板则解法如下所示。一方面本题每次的搜索路径为下、右这两个方向上未使用过的网络;另一方面本题要求的是统计机器人可以进入的方格总数。故每进入一个有效方格时,需要更新统计值,并将该方格标记为已访问过。但需要注意的是本题在回溯之后,即递归返回后不需要撤销所做出的选择。即不能再将之前已经访问的方格从已访问的状态撤销为未访问的状态。否则即会导致重复统计。换言之,在实际解题过程中不能生搬硬套解题模板。要善于理论联系实际、灵活应变。解题模板的作用在于总结经验、沉淀认知、减少解题的思维负担,它并不能完全取代、代替整个思考过程
1 | class Solution { |