数据结构和算法分析

算法面试题 | 回溯算法解题框架

2020-10-01  本文已影响0人  彭旭锐

前言

系列文章
延伸文章
排列 & 组合 & 子集问题 提示 & 题解
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 回溯的三要素

理解了回溯算法的思想，下面我们来分析回溯的关键点。在回溯算法中，需要考虑三个要素：路径、选择列表、结束条件，以走迷宫为例：

回溯就是“走回头路”

要走出这个迷宫，我们需要重复做一件事：选择从一个方向进去尝试。如果走到死胡同则返回上一个分叉口，选择另外一条方向继续尝试。用程序实现出来，这个重复做的事就是递归函数，实际中我们可以遵循一个解题模板 & 思路：

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]。用我们前面介绍的解题模板，这道题并不难：

然而，因为原数组中有两个 1 ，所以结果中会存在一些重复排列，怎么去重呢？一种方法是在得到排列之后，检查结果集合中是否已经有相同的排列，这是一个O(n^2)的比较，显然是不明智的。另一种方法就是寻找重复状态，打从一开始就“有先见之明”地避开一些选择。

我们先说说什么是重复状态？还记得我们说的回溯三要素吗：路径、选择列表、结束条件。通常来说，在这三个要素里面结束条件是固定的，而路径和选择列表会随着每次选择 & 回溯而变化。

也就是说，当我们发现两个状态的路径和选择列表完全相同时，说明这两个状态是完全重复的。以两个重复状态为起点进行递归，最终得到的结果也一定是重复的。在这道题里，我们先对输入执行 快速排序，在之后的每次选择之前，先判断当前状态是否与上一个选择重复，是则直接跳过。

[1]与[1`]重复，[2,1]与[2`,1]重复，最终得到重复结果

当我们在一个选择的分支中确定了最终解后，就没必要去尝试其他的选择了。例如在 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）可以说是回溯算法里最常规的问题了。其中，子集问题本质上也是组合问题。我们先通过一个简单的问题带大家体会 排列 & 组合 的区别：

一排和一堆的区别是什么呢？很明显，一排是有顺序的，而一堆是无顺序的。例如 [A B C] 和 [A C B] 是不同的，而 {A B C} 和 {A C B} 是相同的。

从三个球中取一个、两个、三个的方法

从上面这张图里，其实可以清楚地看到，组合问题是在排列问题的基础上去除重复集合；子集问题是合并了多个不同规模的组合问题。

那么，如何排除元素相同，顺序不同的集合呢？这里提一个很好理解的方法，相信一说出来很多同学都会焕然大悟：“我的初中数学老师就是这么教我的。”

可以看到，只要避免组合之前的元素，就可以避免重复。例如在选择 {B, }之后，就不要组合之前的 A 元素了，否则会造成重复。因为在 {A, } 的分支里，已经存在过 {A, B} 的组合了。因此，我们可以使用一个 from 变量来标示当前状态允许的选择列表范围。

下面给出从 n 个数中取 k 的数的排列 & 组合代码，由于递归解法代码的可解释性更强，读者应优先保证可以熟练地写出递归解法：

复杂度分析：

总共有n!个子问题，每个子问题的时间复杂度 O(n)，因此总的时间复杂度 n*n! 。除了输出数组外，空间复杂度为 O(n)；

总共有 2^n 个子问题，每个子问题的时间复杂度 O(n)，因此总的时间复杂度 n*2^n。除了输出数组外，空间复杂度为 O(n)；

3.2 字典序排列问题

在排列问题中，还有一个字典序排列（Dictionary order）的概念，即：基于字母顺序排列，就像单词在字典中的排列顺序一样，例如 [A B C] 排在 [A C B] 之前。要得到字典序的全排列，递归解法和非递归解法都可以实现。

使用递归解法，只需要保证选择列表按照字母排序，最终得到的全排列就是字典序排序，实现起来也比较简单直观，在 第 1.4 节 已经给出答案了。

使用非递归解法的基本思想是：从当前字符串出发，直接找出字典序下一个排列，例如从 [A B C] 直接找到下一个排列 [A C B]。怎么找呢，可以先简单思考下这个问题：

31. Next Permutation 下一个排列 将给定数字序列重新排列成字典序中下一个更大的排列。

理解了下一个排列的算法之后，写出全排列的算法就不难了。只需要从第一个排列开始依次输出下一个排列，最终就得到了字典序全排列。有兴趣可以到上一节的题解中查看，这里就不贴出来了。

除了求下一个排列外，求第 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 个方向），不过只是多了几个方向而已，没有很大区别。例如，下面这幅图将中心节点相连的白色方格上色：

填充颜色到连通的白色方格

整个解题框架与上一节的 二维平面搜索问题 大体相同，这里着重讲解另一种解法：并查集，在这篇文章里，我们已经详细讲解过并查集的使用场景与解题技巧：《数据结构面试题 | 并查集 & 联合 - 查找算法》

简单来说：并查集适用于处理不相交集合的连通性问题，这正适用于解决 Flood Fill 的连通问题。我们可以将与中心节点相连的节点合并到同一个分量中，全部处理完成后，通过查询并查集便可判断两个节点是否处于相连：

提示： 同时使用路径压缩和按秩合并，查询的时间复杂度接近O(1)

6. 总结

回溯算法的思想并不复杂，但是确实高频考点；熟练掌握回溯算法，对于理解动态规划算法也很有帮助，学习优先级较高。

参考资料

推荐阅读

感谢喜欢！你的点赞是对我最大的鼓励！欢迎关注彭旭锐的GitHub！

上一篇下一篇

猜你喜欢

热点阅读