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

前言

• 回溯算法的思想并不复杂，但是在回溯基础上的不少变型题也是面试高频考点，掌握基本的解题框架很重要。
• 在这篇文章里，我将梳理回溯算法的基本概念 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章

• 《算法面试题 | 链表问题总结》
• 《算法面试题 | 链表相交 & 成环问题》
• 《算法面试题 | 回溯算法解题框架》
• 《数据结构面试题 | 并查集 & 联合 - 查找算法》
• 《数据结构面试题 | 二叉树基础》

延伸文章

• 算法面试题 | 高楼丢鸡蛋（源自谷歌面试题）

目录

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

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

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

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 的数的排列 & 组合代码，由于递归解法代码的可解释性更强，读者应优先保证可以熟练地写出递归解法：

复杂度分析：

• 全排列

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

• 组合

总共有 2n2^n2n 个子问题，每个子问题的时间复杂度 O(n)O(n)O(n)，因此总的时间复杂度 n∗2nn*2^nn∗2n。除了输出数组外，空间复杂度为 O(n)O(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 个排列

除了求下一个排列外，求第 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)O(1)O(1)

6. 总结

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