⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。
本文是数据结构与算法系列的第 6 篇文章，完整文章目录请移步到文章末尾~
前言
-
回溯算法的思想并不复杂，但是在回溯基础上的不少变型题也是面试高频考点，掌握基本的解题框架很重要；
-
在这篇文章里，我将梳理回溯算法的基本概念 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
排列 & 组合 & 子集问题 | 提示 & 题解 |
|---|---|
| 46. 全排列 Permutations | 【题解】 |
| 47. 全排列 II Permutations II | 【题解】 |
| 39. 组合总和 Combination Sum | 【题解】 |
| 40. 组合总和 Combination Sum II | 【题解】 |
| 78.子集 Subsets | 【题解】 |
| 90. 子集 II Subsets II | 【题解】 |
| 784. 字母大小写全排列 Letter Case Permutation | 【题解】 |
| 386. 字典序排数 Lexicographical Numbers | 【题解】 |
| 17. 电话号码的字母组合 Letter Combinations of a Phone Number | 【题解】 |
| 22. 括号生成 Generate Parentheses | 【题解】 |
字典序排列 | 提示 & 题解 |
|---|---|
| 31. 下一个排列 Next Permutation | 【题解】 |
| 60. 第 k 个排列 Permutation Sequence | 【题解】 |
| 440. 字典序的第K小数字 K-th Smallest in Lexicographical Order |
二维平面搜索 | 提示 & 题解 |
|---|---|
| 79. 单词搜索 Word Search | 【题解】 |
| 212. 单词搜索 II Word Search II |
Flood Fill | 提示 & 题解 |
|---|---|
| 733. 图像渲染 Flood Fill | 【题解】 |
| 200. 岛屿数量 Number of Islands | 【题解】 |
| 130. 被围绕的区域 Surrounded Regions | 【题解】 |
| 44. 通配符匹配 Wildcard Matching | |
| 10. 正则表达式匹配 Regular Expression Matching | |
| 488. 祖玛游戏 Zuma Game | |
| 529. 扫雷游戏 Minesweeper |
其他 | 提示 & 题解 |
|---|---|
| 51. N皇后 N-Queens | |
| 52. N皇后 II N-Queens II | |
| 37. 解数独 Sudoku Solver | |
| 301. 删除无效括号 Remove Invalid Parentheses | |
| 1249. 最小数量的移除无效括号 Minimum Remove to Make Valid Parentheses |
目录
1. 概述
1.1 回溯思想
回溯算法（Backtrack）是一种试错思想，本质上是深度优先搜索。即：从问题的某一种状态出发，依次尝试现有状态可以做出的选择从而进入下一个状态。递归这个过程，如果在某个状态无法做更多选择，或者已经找到目标答案时，则回退一步甚至多步重新尝试，直到最终所有选择都尝试过。
整个过程就像走迷宫一样，当我们遇到一个分叉口时，可以选择从一个方向进去尝试。如果走到死胡同则返回上一个分叉口，选择另外一条方向继续尝试，直到发现没有出口，或者找到出口。
1.2 回溯的三要素
理解了回溯算法的思想，下面我们来分析回溯的关键点。在回溯算法中，需要考虑三个要素：路径、选择列表、结束条件，以走迷宫为例：
- 1. 路径：已经做出的选择
- 2. 选择列表：当前状态可以做出的选择
- 3. 结束条件：选择列表为空，或者找到目标
要走出这个迷宫，我们需要重复做一件事：选择从一个方向进去尝试。如果走到死胡同则返回上一个分叉口，选择另外一条方向继续尝试。用程序实现出来，这个重复做的事就是递归函数，实际中我们可以遵循一个解题模板 & 思路：
fun backtrack(){
1. 判断当前状态是否满足终止条件
if(终止条件){
return solution
}
2. 否则遍历选择列表
for(选择 in 选择列表){
3. 做出选择
solution.push(选择)
4. 递归
backtrack()
5. 回溯（撤销选择）
stack.pop(选择)
}
}
需要注意的是，解题框架 & 思路不是死板的，应根据具体问题具体分析。例如：回溯（撤销选择）并不是必须的，第 3.2 节第 k 个排序、第 5 节岛屿数量问题中，它们在深层函数返回后没有必要回溯。
1.3 回溯剪枝
由于回溯算法的时间复杂度非常高，当我们遇到一个分支时，如果“有先见之明”，能够知道某个选择最终一定无法找到答案，那么就不应该去尝试走这条路径，这个步骤叫作剪枝。
那么，怎么找到这个“先见之明”呢？经过我的总结，大概有以下几种情况：
- 重复状态
例如：47. Permutations II 全排列 II（用重复数字） 这道题给定一个可包含重复数字的序列，要求返回所有不重复的全排列，例如输入[1,1,2]预期的输出为[1,1,2]、[1,2,1]、[2,1,1]。用我们前面介绍的解题模板，这道题并不难：
class Solution {
fun permute(nums: IntArray): List<List<Int>> {
val result = ArrayList<List<Int>>()
// 选择列表
val useds = BooleanArray(nums.size) { false }
// 路径
val track = LinkedList<Int>()
fun backtrack() {
// 终止条件
if (track.size == nums.size) {
result.add(ArrayList<Int>(track))
return
}
for ((index, used) in useds.withIndex()) {
if (!used) {
// 做出选择
track.push(nums[index])
useds[index] = true
backtrack()
// 回溯
track.pop()
useds[index] = false
}
}
}
backtrack()
return result
}
}
然而，因为原数组中有两个 1 ，所以结果中会存在一些重复排列，怎么去重呢？一种方法是在得到排列之后，检查结果集合中是否已经有相同的排列，这是一个的比较，显然是不明智的。另一种方法就是寻找重复状态，打从一开始就“有先见之明”地避开一些选择。
我们先说说什么是重复状态？还记得我们说的回溯三要素吗：路径、选择列表、结束条件。通常来说，在这三个要素里面结束条件是固定的，而路径和选择列表会随着每次选择 & 回溯而变化。
也就是说，当我们发现两个状态的路径和选择列表完全相同时，说明这两个状态是完全重复的。以两个重复状态为起点进行递归，最终得到的结果也一定是重复的。在这道题里，我们先对输入执行 快速排序，在之后的每次选择之前，先判断当前状态是否与上一个选择重复，是则直接跳过。
class Solution {
fun permuteUnique(nums: IntArray): List<List<Int>> {
val result = ArrayList<LinkedList<Int>>()
if(nums.size <= 0){
result.add(LinkedList<Int>())
return result
}
// 排序
Arrays.sort(nums)
// 选择列表
val used = BooleanArray(nums.size){false}
// 路径
val track = LinkedList<Int>()
fun backtrack(){
// 终止条件
if(track.size >= nums.size){
result.add(LinkedList<Int>(track))
return
}
for((index,num) in nums.withIndex()){
if(used[index]){
continue
}
if(index > 0 && !used[index - 1] && nums[index] == nums[index - 1]){
continue
}
// 做出选择
used[index] = true
track.push(num)
// 递归
backtrack()
// 回溯
used[index] = false
track.pop()
}
}
backtrack()
return result
}
}
- 最终解确定
当我们在一个选择的分支中确定了最终解后，就没必要去尝试其他的选择了。例如在 79. Word Search 单词搜索 中，当确定单词存在时，就没必要继续搜索了，在 第 4 节 会专门分析这道题。
fun backtrack(...){
for (选择 in 选择列表) {
1. 做出选择
2. 递归
val match = backtrack(...)
3. 回溯
if (match) {
return true
}
}
}
- 无效选择
当我们可以根据已知条件判断某个选择无法找到最终解时，就没必要去尝试这个选择了。例如：39. Combination Sum 组合总和、60. Permutation Sequence 第 k 个排列
3. 排列 & 组合 & 子集问题
3.1 排列 & 组合问题
**排列（permutation）& 组合（combination）& 子集（subset）**可以说是回溯算法里最常规的问题了。其中，子集问题本质上也是组合问题。我们先通过一个简单的问题带大家体会 排列 & 组合 的区别：
- 排列问题： 有 3 个不同的小球 A，B，C，从中取出 2 个放称一排，有几种方法？
- 组合问题： 有 3 个不同的小球 A，B，C，从中取出 2 个放成一堆，有几种方法？
一排和一堆的区别是什么呢？很明显，一排是有顺序的，而一堆是无顺序的。例如 [A B C] 和 [A C B] 是不同的，而 {A B C} 和 {A C B} 是相同的。
从上面这张图里，其实可以清楚地看到，组合问题是在排列问题的基础上去除重复集合；子集问题是合并了多个不同规模的组合问题。
那么，如何排除元素相同，顺序不同的集合呢？这里提一个很好理解的方法，相信一说出来很多同学都会焕然大悟：“我的初中数学老师就是这么教我的。”
可以看到，只要避免组合之前的元素，就可以避免重复。例如在选择 {B, }之后，就不要组合之前的 A 元素了，否则会造成重复。因为在 {A, } 的分支里，已经存在过 {A, B} 的组合了。因此，我们可以使用一个 from 变量来标示当前状态允许的选择列表范围。
下面给出从 n 个数中取 k 的数的排列 & 组合代码，由于递归解法代码的可解释性更强，读者应优先保证可以熟练地写出递归解法：
复杂度分析：
- 全排列
总共有个子问题，每个子问题的时间复杂度 ，因此总的时间复杂度 。除了输出数组外，空间复杂度为 ；
- 组合
总共有 个子问题，每个子问题的时间复杂度 ，因此总的时间复杂度 。除了输出数组外，空间复杂度为 ；
3.2 字典序排列问题
在排列问题中，还有一个**字典序排列（Dictionary order）**的概念，即：基于字母顺序排列，就像单词在字典中的排列顺序一样，例如 [A B C] 排在 [A C B] 之前。要得到字典序的全排列，递归解法和非递归解法都可以实现。
使用递归解法，只需要保证选择列表按照字母排序，最终得到的全排列就是字典序排序，实现起来也比较简单直观，在 第 1.4 节 已经给出答案了。
使用非递归解法的基本思想是：从当前字符串出发，直接找出字典序下一个排列，例如从 [A B C] 直接找到下一个排列 [A C B]。怎么找呢，可以先简单思考下这个问题：
- 下一个排列
31. Next Permutation 下一个排列 将给定数字序列重新排列成字典序中下一个更大的排列。
理解了下一个排列的算法之后，写出全排列的算法就不难了。只需要从第一个排列开始依次输出下一个排列，最终就得到了字典序全排列。有兴趣可以到上一节的题解中查看，这里就不贴出来了。
- 第 k 个排列
除了求下一个排列外，求第 k 个排列也是很常见了。例如：60. Permutation Sequence 第 k 个排列、440. K-th Smallest in Lexicographical Order 字典序的第K小数字。基本思想是：通过计算阶乘，提前知道这一个分支的叶子节点个数，如果 k 不在这个分支上则剪枝：
4. 二维平面搜索问题
文章开头提到的走迷宫问题，其实就是在二维平面上的回溯算法问题，终止条件时当前位置为终点。既然是回溯算法，怎么都逃不出我们反复强调的三要素：路径 & 选择列表 & 终止条件：
4.1 路径 - 二维数组 useds
在全排列问题中，我们使用了一维布尔数组 used，用来标记已经走过的路径。同样地，在二维平面里，我们需要使用二维布尔数组，来标记已经走过的路径。
1. 一维数组 int[] useds
2. 二维数组 int[][] useds
4.2 选择列表 - 偏移量数组
在二维平面上搜索时，一个点的选择列表就是它的上下左右方向（除了来的方向），为了方便编码，可以使用一个偏移量数组，偏移量数组内的 4 个偏移的顺序是无关紧要；
int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
4.3 检查边界
二维平面通常是有边界的，因此可以写一个函数判断当前输入位置是否越界：
private boolean check(int row, int column) {
return row >= 0 && row < m && column >= 0 && column < n;
}
有了前面的铺垫，我们来看这道题：79. Word Search 单词搜索 就比较好理解了。
5. Flood Fill 问题
Flood Fill（泛洪填充，或称 Seed Fill 种子填充），是上一节二维平面搜索问题的进阶版本。即：在二维平面上找出满足条件的相连节点。
所谓相连节点，指的是两个节点上下左右 4 个方向存在相连的节点。有的题目会扩展到 8 个方向（斜对角的 4 个方向），不过只是多了几个方向而已，没有很大区别。例如，下面这幅图将中心节点相连的白色方格上色：
整个解题框架与上一节的 二维平面搜索问题 大体相同，这里着重讲解另一种解法：并查集，在这篇文章里，我们已经详细讲解过并查集的使用场景与解题技巧：数据结构与算法 #14 使用并查集解决 “朋友圈” 问题
简单来说：并查集适用于处理不相交集合的连通性问题，这正适用于解决 Flood Fill 的连通问题。我们可以将与中心节点相连的节点合并到同一个分量中，全部处理完成后，通过查询并查集便可判断两个节点是否处于相连：
提示： 同时使用路径压缩和按秩合并，查询的时间复杂度接近
6. 总结
回溯算法的思想并不复杂，但是确实高频考点；熟练掌握回溯算法，对于理解动态规划算法也很有帮助，学习优先级较高。
参考资料
- 《回溯法》 —— 维基百科
- 《Flood Fill》 —— 维基百科
- 《回溯算法入门级详解 + 练习（全排列 I）》 —— liweiwei 著
- 《回溯搜索 + 剪枝（全排列 II）》 —— liweiwei 著
- 《在二维平面上使用回溯法（单词搜索 I）》 —— liweiwei 著
- 《回溯算法》 —— liweiwei 著
- 《回溯算法详解》 —— labuladong 著
- 《FloodFill算法详解及应用》 —— labuladong 著
- 《300分钟搞定算法面试》 —— 力扣&拉勾网 出品
推荐阅读
数据结构与算法系列完整目录如下（2023/07/11 更新）：
Java & Android 集合框架系列文章: 跳转阅读
LeetCode 上分之旅系列文章：跳转阅读
⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~
