LeetCode（八）：回溯算法

当你遇到需要“枚举所有可能”的问题时，回溯算法几乎是不二之选——无论是全排列、子集、合法棋盘布局，还是网格中的路径搜索，它都能派上用场。简单来说，回溯是一种“带脑子的暴力搜索”：它一步步构建候选解，一旦发现当前路径违反约束、无法通向合法答案，就立刻放弃，并撤销上一步的选择，恢复到干净的状态，再尝试其他分支。整个过程可以浓缩为三个动作：选择 → 递归 → 撤销。

掌握这个节奏，你就能轻松应对 LeetCode 上约九成的“找出所有……”类题目，比如全排列、组合、子集、单词搜索、N 皇后和数独等。本文将先详解通用模板，再通过六道经典题展示完整实现、递归树图示、复杂度分析、剪枝技巧，以及新手写回溯时几乎必然会踩的坑。

回溯算法到底是什么#

回溯本质上是在一棵隐式的搜索树上进行深度优先遍历。每个节点代表一个部分解（即当前的 path），每条边对应一次具体决策（例如选择某个元素、在某列放置皇后、在格子中填入数字）。当到达叶子节点且满足目标条件时，就记录该解；若中途发现违反约束，则立即停止向下探索并回退。所谓“回溯”，正是指显式地撤销上一步决策，使状态恢复到递归调用前的样子，从而能干净地探索其他分支。

这一点正是回溯与普通 DFS 的关键区别：图遍历中每个节点仅访问一次，无需撤销任何操作；而回溯算法会在指数级数量的分支间反复复用同一份 path 和 used[] 等数据结构。若不显式恢复状态，后续递归将基于被污染的数据执行，导致结果完全错误。

何时使用回溯？

题目要求“返回所有……”：如所有排列、组合、子集、划分、合法括号序列等。
属于约束满足问题（CSP）：如 N 皇后、数独、图着色。
搜索空间呈指数级，但可通过检查部分解提前剪掉大量无效分支。
只需找到一个可行解及其构造过程，且贪心或动态规划不适用。

何时不该用？

仅需计数或最优值，且子问题存在重叠 → 改用动态规划（DP）。
状态空间足够小，可直接迭代枚举。
问题可转化为 BFS 最短路径或已知图算法。

通用模板#

本文所有解法都源自同一个模板。记住这个结构，再根据具体问题填充四个关键部分即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def backtrack(path, state):
    # 1. 目标：是否已经构成完整解？保存一份「快照」后返回。
    if is_goal(path, state):
        result.append(path[:])          # path[:] 是快照，不是引用
        return

    # 2..4. 遍历当前节点的所有可选决策。
    for choice in choices(state):
        if not is_valid(choice, path, state):
            continue                    # 剪枝

        path.append(choice)             # 2. 选择
        update(state, choice)
        backtrack(path, state)          # 3. 递归
        path.pop()                      # 4. 撤销
        undo(state, choice)

你需要准确处理以下四点：

is_goal：何时认为 path 已构成完整答案？
choices：当前状态下有哪些可选操作？（通常由 start 索引、used[] 数组，或两者共同控制）
is_valid：哪些选择在此分支下非法？（务必尽早剪枝）
update / undo：递归前做的任何修改，回溯时必须完全还原。这是新手最容易出错的地方。

关于 path[:] 的细节：若直接写 result.append(path)，存入的是对同一列表的引用。由于 path 在递归过程中会被不断修改，最终 result 中的所有元素都会指向一个空列表。因此必须使用 path[:]、path.copy() 或 list(path) 创建副本。

回溯 vs DFS：一句话说清区别#

DFS 的核心是“遍历”——每个节点只访问一次，不修改已走过的结构，仅靠递归栈就能维持状态。回溯的核心是“构造”——同一份 path 在递归向下时被修改，在回溯向上时被还原，从而能在指数级分支中高效复用，避免频繁拷贝。简言之，回溯借用了 DFS 的遍历方式，但额外引入了“选择—递归—撤销”的纪律性操作。

LeetCode 46 —— 全排列#

给定一个不含重复数字的数组 nums，返回所有可能的排列。

示例：nums = [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

模板怎么填#

目标：len(path) == len(nums)。
选择：任选一个尚未使用的数字。
合法性：not used[i]。
状态：用布尔数组 used[] 标记元素是否已被选用，递归前设为 True，回溯时恢复为 False。

对于 [1,2,3]，其递归树呈标准的 3-2-1 扇形结构：第一层有 3 种选择，第二层剩 2 种，最后一层只剩 1 种，最终生成 3! = 6 个叶子节点，恰好对应所有排列。

代码实现#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result: List[List[int]] = []
        path: List[int] = []
        used = [False] * n

        def backtrack() -> None:
            if len(path) == n:                  # 目标
                result.append(path[:])          # 拷贝一份，不要存引用
                return
            for i in range(n):
                if used[i]:                     # 剪枝：已经在路径里了
                    continue
                used[i] = True                  # 选择
                path.append(nums[i])
                backtrack()                     # 递归
                path.pop()                      # 撤销
                used[i] = False

        backtrack()
        return result

复杂度分析#

共有 n! 种排列，每种拷贝到结果需 O(n) 时间，总时间复杂度为 O(n \cdot n!)。递归栈和 path 数组各占 O(n) 辅助空间（输出结果不计入）。

为何是 n!？第 0 层有 n 个选择，第 1 层有 n−1 个，依此类推，叶子总数为 n × (n−1) × ⋯ × 1 = n!。

LeetCode 39 —— 组合总和#

给定一个不含重复元素的正整数数组 candidates 和目标值 target，返回所有元素和为 target 的组合。每个数字可无限次重复使用。

示例：candidates = [2,3,6,7], target = 7 → [[2,2,3], [7]]。

模板怎么填#

目标：remain == 0。
剪枝条件：若 remain < 0，立即放弃该分支。
避免重复：这是难点。[2,3] 与 [3,2] 视为同一组合（顺序无关）。标准解法是引入 start 索引，规定“从此分支起，只能选择下标 ≥ start 的元素”，从而强制组合按固定顺序生成，确保每种组合仅出现一次。
允许重复选择：递归时传入 i（而非 i+1），使同一数字可被多次选用。

下方决策树展示了剪枝效果：每个红色 X 表示因 remain < 0 被剪掉的分支。相比穷举所有 4^k 种可能，剪枝大幅压缩了搜索空间。

代码实现#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int, remain: int) -> None:
            if remain == 0:                     # 目标
                result.append(path[:])
                return
            if remain < 0:                      # 剪枝：超过目标
                return
            for i in range(start, len(candidates)):
                path.append(candidates[i])      # 选择
                backtrack(i, remain - candidates[i])  # 递归，i（不是 i+1）允许复用
                path.pop()                      # 撤销

        backtrack(0, target)
        return result

排序后提前退出的优化#

若先对 candidates 排序，内层循环可在 candidates[i] > remain 时直接 break（而非 continue），因为后续元素更大，不可能满足条件。在对抗性输入下，此优化可带来显著加速。

1
2
3
4
5
6
7
candidates.sort()
for i in range(start, len(candidates)):
    if candidates[i] > remain:
        break                                   # 后面的候选数只会更大，直接退出
    path.append(candidates[i])
    backtrack(i, remain - candidates[i])
    path.pop()

复杂度分析#

由于允许重复使用，路径长度可能超过输入规模，故难以写出简洁的上界。设最小候选数为 m，则路径最长为 target / m，每步最多 n 个选择，最坏时间复杂度为 O(n^{target/m})。实际中剪枝会大幅削减分支。空间复杂度为 O(target / m)，对应最大递归深度。

LeetCode 78 —— 子集#

给定一个不含重复元素的整数数组 nums，返回其所有 2^n 个子集（幂集）。

示例：nums = [1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]。

模板怎么填#

目标：此处无单一终止条件——递归树的每个节点都是合法子集（包括根节点的空集）。因此每次进入函数就保存当前 path。
选择：从 i >= start 开始选取 nums[i]，递归时令 start = i + 1，确保元素不重复使用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            result.append(path[:])              # 每个节点都是合法子集
            for i in range(start, len(nums)):
                path.append(nums[i])            # 选择
                backtrack(i + 1)                # 递归：每个元素至多用一次
                path.pop()                      # 撤销

        backtrack(0)
        return result

另一种更直观的思路是“对每个元素，决定包含或跳过”：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def subsets_binary(nums):
    result, path = [], []
    n = len(nums)
    def backtrack(i: int) -> None:
        if i == n:
            result.append(path[:])
            return
        backtrack(i + 1)                        # 不选 nums[i]
        path.append(nums[i])                    # 选 nums[i]
        backtrack(i + 1)
        path.pop()
    backtrack(0)
    return result

两种实现的时间复杂度均为 O(n \cdot 2^n)，辅助空间为 O(n)。

LeetCode 79 —— 单词搜索#

给定 m × n 字符网格和字符串 word，判断能否通过水平或垂直相邻的格子拼出 word，每个格子至多使用一次。

这是回溯在二维网格上的应用。每步选择“移动到哪个邻居”，约束为：目标字符匹配 word 的下一位，且该格子未被当前路径占用。目标是成功匹配 word 的最后一个字符。

最简洁的路径标记方式是原地修改网格：进入格子时将其改为哨兵字符（如 '#'），离开时恢复原值。这正是“选择/撤销”机制在二维状态下的体现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(r: int, c: int, k: int) -> bool:
            if k == len(word):                  # 目标达成：完整匹配了 word
                return True
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[k]:
                return False                    # 越界或字符不匹配 -> 剪枝

            tmp, board[r][c] = board[r][c], '#'  # 选择：标记为已访问
            found = (dfs(r + 1, c, k + 1) or
                     dfs(r - 1, c, k + 1) or
                     dfs(r, c + 1, k + 1) or
                     dfs(r, c - 1, k + 1))
            board[r][c] = tmp                    # 撤销：恢复原字符
            return found

        for r in range(m):
            for c in range(n):
                if dfs(r, c, 0):
                    return True
        return False

时间复杂度最坏为 O(m \cdot n \cdot 4^L)（L = len(word)），因起点有 m·n 种，每步最多四向扩展，路径长至多 L。但实际中，字符不匹配会提前剪枝，性能远优于理论值。空间复杂度为 O(L)，对应递归深度。

LeetCode 51 —— N 皇后#

在 n × n 棋盘上放置 n 个皇后，使其互不攻击（不同行、列、对角线），返回所有方案。

关键技巧在于对角线编码。对任意格子 (r, c)：

主对角线（↘）上所有格子的 r - c 相同。
副对角线（↙）上所有格子的 r + c 相同。

借此，可用 O(1) 的集合操作判断对角线冲突，无需扫描棋盘。结合“每行仅放一皇后”自动规避行冲突，只需维护列、主对角线、副对角线三个 O(1) 约束集，即可将搜索空间从朴素的 n^n 大幅压缩。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result: List[List[str]] = []
        board = [['.'] * n for _ in range(n)]
        cols: set[int] = set()  # 列占用情况
        diag1: set[int] = set() # 主对角线占用情况（r - c）
        diag2: set[int] = set() # 副对角线占用情况（r + c）

        def backtrack(row: int) -> None:
            if row == n:  # 找到一个完整解
                result.append([''.join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue  # 剪枝：列或对角线被占用
                board[row][col] = 'Q'  # 放置皇后
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                backtrack(row + 1)  # 递归处理下一行
                board[row][col] = '.'  # 撤销放置
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        backtrack(0)
        return result

其渐近复杂度难以闭式表达。粗略上界为 O(n!)（因每行至少排除下一列的一个位置），但对角线剪枝使实际复杂度显著降低。解的数量增长约为 n! / n^c，具体见 OEIS A000170。

LeetCode 37 —— 解数独#

原地解数独：1–9 在每行、每列、每个 3×3 宫格中恰好出现一次。

数独是“强剪枝回溯”的典范。尽管最坏搜索空间巨大，但实际题目中多数空格仅有 1–2 个合法候选，因此算法通常在毫秒内完成。

基本思路：“找下一个空格，尝试所有合法数字，递归填入”。若失败，擦除该格并尝试下一候选；若全部失败，则回溯至上一层。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        rows  = [set() for _ in range(9)]
        cols  = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        empty: List[tuple[int, int]] = []

        # 预处理已填数字和空格位置。
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == '.':
                    empty.append((r, c))
                else:
                    rows[r].add(v); cols[c].add(v); boxes[(r // 3) * 3 + c // 3].add(v)

        def backtrack(k: int) -> bool:
            if k == len(empty):                 # 所有空格都填完了，返回成功
                return True
            r, c = empty[k]
            b = (r // 3) * 3 + c // 3
            for d in '123456789':
                if d in rows[r] or d in cols[c] or d in boxes[b]:
                    continue                    # 不合法，跳过
                board[r][c] = d                 # 选择
                rows[r].add(d); cols[c].add(d); boxes[b].add(d)
                if backtrack(k + 1):            # 递归
                    return True                 # 找到解了，直接返回
                board[r][c] = '.'               # 撤销
                rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
            return False                        # 当前格子无解，回溯

        backtrack(0)

两点值得注意：

提前终止：一旦找到解，立即 return True 并逐层返回，停止整棵树搜索。这对“只需一个解”的问题极为高效。
预处理空格：提前将所有空格存入 empty[]，避免每次递归扫描棋盘（将 O(81) 降至 O(1)）。更进一步可采用 MRV（最小剩余值）启发式：优先填充合法候选最少的空格，显著降低底部分支因子。

最坏复杂度为空格数的指数级，但强约束使 9×9 数独在实践中几乎总能毫秒级解决。

真正实用的剪枝技巧#

递归前的 is_valid 检查是区分暴力枚举与高效算法的关键。以下五种剪枝技巧最为常用：

约束剪枝：if not is_valid(choice): continue。务必在递归前执行，而非之后。
边界剪枝：如目标和问题中，若 remain < 0 或剩余元素总和不足 remain，直接返回。
排序 + 提前退出：先排序输入，当 candidates[i] > remain 时直接 break（因后续更大）。
跳过重复元素：先排序，循环中加 if i > start and nums[i] == nums[i-1]: continue。这是“组合总和 II”和“全排列 II”的标准去重法。
对称性剪枝：如 N 皇后（n ≥ 4 时），限制首行选择范围至一半，其余解通过对称生成。

这些技巧单独或组合使用，可大幅削减搜索空间。

复杂度速查表#

问题	时间复杂度	空间复杂度（辅助）	原因
全排列	`O(n \cdot n!)`	`O(n)`	`n!` 种排列，每种拷贝耗时 `O(n)`
组合总和	最坏 `O(n^{target/m})`	`O(target)`	`m` 为最小候选数，剪枝显著优化
子集	`O(n \cdot 2^n)`	`O(n)`	`2^n` 个子集，每个拷贝耗时 `O(n)`
单词搜索	`O(m n \cdot 4^L)`	`O(L)`	起点任意，每步最多四向扩展
N 皇后	约 `O(n!)`（最坏）	`O(n)`	按行递归 + 对角线约束剪枝
数独	最坏指数级	`O(81)`	强约束大幅削减搜索空间，实际运行极快

你大概率会踩的几个坑#

坑 1：保存引用而非副本。

1
2
result.append(path)        # 错：最后所有结果都指向同一个空列表
result.append(path[:])     # 对

坑 2：忘记撤销操作。

1
path.append(c); backtrack();  # 漏掉 path.pop()，导致下一轮循环带着脏数据继续

坑 3：状态恢复不完整： 若递归前修改了 used[i]、棋盘或对角线集合，回溯时必须全部还原。养成习惯：递归调用后的每一行代码，都应镜像对应调用前的某一行。

坑 4：先添加后判断合法性。 务必在 path.append(choice) 之前检查 is_valid(choice)，否则剪枝毫无意义。

坑 5：组合与排列的循环起点混淆。 组合需 start 参数保证顺序；排列需 used[] 标记使用情况。弄反会导致重复或遗漏。

坑 6：数独中每次都扫描找空格。 朴素写法在每次递归时用嵌套循环找空格，应提前预处理 empty[] 列表，将复杂度从 O(81) 降至 O(1)。

常见问答（Q&A）#

Q1：回溯和 DFS 到底有什么区别？
DFS 是遍历，每个节点只访问一次，结构不变；回溯是构造，复用同一份状态并在回溯时恢复。回溯借用了 DFS 的遍历方式，但增加了“选择与撤销”的机制。

Q2：回溯和动态规划怎么选？
需要“所有解”用回溯；需要“计数”或“最优值”且子问题重叠用 DP。有时两者皆可，但 DP 更快（如统计路径数 vs 列举路径）。

Q3：为什么要写 path[:] 而不是 path？
path 是引用，直接保存会导致 result 中所有元素最终指向同一空列表。path[:] 才能保存当前状态的快照。

Q4：输入有重复时怎么去重？
先排序，循环中加 if i > start and nums[i] == nums[i-1]: continue。这会跳过同层重复兄弟，但不影响不同层的相同元素。

Q5：组合和排列代码上有什么区别？
排列用 used[] 标记已选元素，循环从 0 开始；组合用 start 索引控制顺序，确保结果按规范生成。

Q6：代码正确但超时，如何优化？
一查是否在递归前剪枝；二看合法性判断是否 O(1)（用集合/数组而非 in path）；三能否排序后用 break 替代 continue。

Q7：回溯能改成迭代吗？
可以，用显式栈保存 (path, state) 对。但递归通常更简洁，迭代仅在递归深度过大时有用。

Q8：只要找到一个解怎么写？
让递归函数返回 bool 或解本身，找到目标立即返回 True 并逐层传递，终止后续搜索。

Q9：数独遇难题特别慢，如何优化？
用 MRV（最小剩余值）策略：优先填合法候选最少的空格。配合 rows/cols/boxes 集合，可大幅减少底部分支。

Q10：这几道题的学习顺序怎么安排？
建议顺序：全排列 → 子集 → 组合总和 → 单词搜索 → N 皇后 → 数独。每道题引入一个新概念：used[] → 每个节点都保存 → start 索引 + 复用 → 网格遍历 → 多约束集 → 提前终止 + 启发式。

总结#

回溯算法的核心就一个节奏——选择、递归、撤销，再套上约束检查。关键在于识别模板中的四个部分：目标条件、可选项、合法性判断、状态维护，并根据问题填充。全排列展示了 used[] 的用法；子集说明“每个节点都是解”；组合引入 start 索引保证顺序；单词搜索将模板迁移到二维网格；N 皇后用对角线公式实现 O(1) 冲突检测；数独则展示强剪枝如何将天文数字般的搜索空间压缩至毫秒级。

如果本文只能让你记住一句话，那就是：递归下去改了什么，回来时就得原样改回去。 这条原则是回溯的灵魂——守住它，剩下的不过是按需填模板罢了。

LeetCode（八）：回溯算法

回溯算法到底是什么#

通用模板#

回溯 vs DFS：一句话说清区别#

LeetCode 46 —— 全排列#

模板怎么填#

代码实现#

复杂度分析#

LeetCode 39 —— 组合总和#

模板怎么填#

代码实现#

排序后提前退出的优化#

复杂度分析#

LeetCode 78 —— 子集#

模板怎么填#

LeetCode 79 —— 单词搜索#

LeetCode 51 —— N 皇后#

LeetCode 37 —— 解数独#

真正实用的剪枝技巧#

复杂度速查表#

你大概率会踩的几个坑#

常见问答（Q&A）#

总结#

LeetCode 算法模式 10 篇

读有所得？