回溯算法是处理"列举所有可能"这一类问题的标准武器：所有排列、所有子集、所有合法棋盘、网格里所有路径。它的本质是带剪枝的暴力搜索——一次走一步，碰到死路立刻退回去，把刚才做的选择"撤回"，让下一条分支看到一个干净的状态。整套方法只有三步：

选择 -> 递归 -> 撤销

一个节奏，可以打通全排列、组合、子集、单词搜索、N 皇后、数独。LeetCode 上"找出所有……“这类题里，大约九成都套这个模板。本文先把模板讲透，再用六道经典题逐一示范代码、递归树、复杂度证明、剪枝技巧，以及第一次写回溯时几乎所有人都会踩的坑。

系列导航

LeetCode 算法精讲系列（共 10 篇）：

哈希表（Two Sum、最长连续序列、字母异位词分组）
双指针技巧（对撞、快慢、滑动窗口）
链表操作（反转、环检测、合并）
二叉树遍历与递归（前/中/后序、LCA）
动态规划入门（一维/二维 DP、状态转移）
二分查找进阶（整数、实数、答案二分）
动态规划续篇
-> 回溯算法（排列、组合、剪枝）<- 当前位置
栈与队列（单调栈、优先队列、双端队列）
贪心与位运算

回溯算法到底是什么

回溯是一棵隐式搜索树上的深度优先搜索。每个节点是一个"部分解”（当前的 path），每条边是一次具体的决策（把某个数加进来、在某列摆个皇后、在格子里写个数字）。走到一个满足目标的叶子，就把答案记下来；走到一个违反约束的节点，就停下来回退。所谓"回溯"，就是显式地把刚才那一步撤回，让算法能够带着一个干净的状态去试旁边那条分支。

这正是回溯和普通 DFS 的本质区别。图遍历每个节点只访问一次，不需要撤销什么；可回溯算法在指数级多的分支之间共用同一份 path 和 used[]，如果不在返回时把状态恢复回去，下一次调用看到的就是一锅乱炖。

适合用回溯的问题特征：

题目要求"返回所有……"：所有排列、所有组合、所有子集、所有划分、所有合法括号组合等。
约束满足问题：N 皇后、数独、图着色。
搜索空间是指数级的，但绝大多数分支可以靠"部分约束"提前砍掉。
只需要一个解，外加一条具体的构造路径，且贪心或 DP 不适用。

不适合的场景：

只要计数或最优值，且子问题有大量重叠 -> 用 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 被 pop 干净，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!？根节点有 n 种选择，下一层 n-1 种，再下一层 n-2……乘起来正好是 n \cdot (n-1) \cdots 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

排序加 break 的优化

把 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]]。

模板怎么填

目标：没有单一的目标条件——递归树每一个节点都是一个合法子集，包括根（空集）。所以一进入函数就保存一次。
选择：从 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 x n 的字符网格和一个字符串 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 \cdot n 个起点，每条路径最长 L，每步分四个方向）。开头的字符不匹配检查在实际数据上把绝大部分分支都剪掉了。空间 O(L) 对应递归深度。

LeetCode 51：N 皇后

在 n x 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

N 皇后的渐近复杂度很难写出闭式：宽松上界是 O(n!)，因为每一行至少消掉下一行的一列；实际有对角线剪枝后还要更小。解的数量本身就是个有名的非平凡数列（OEIS A000170）。

LeetCode 37：解数独

原地解一道数独：1-9 在每一行、每一列、每个 3x3 宫格里都恰好出现一次。

数独是"强剪枝回溯"最经典的教学例。绝大多数空格在当前局面下其实只有一两个合法候选，所以最坏情况下的搜索树虽然天文数字大，真实题目几毫秒就能解完。

模式很直接：找下一个空格 -> 试每个合法数字 -> 递归。走到死胡同就把空格擦掉换下一个数字；如果所有数字都不行，就 return False，让上层把它的格子也擦掉。

 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[] 算出来，而不是在 backtrack 里现扫下一个空格。这把每一步从 O(81) 降到 O(1)。再进一步可以加 MRV（Minimum Remaining Values）启发式：每次挑当前合法候选最少的空格优先填，能把分支因子在树底部砍得很狠。

最坏复杂度是空格数的指数；但因为约束剪枝太强，9x9 数独基本毫秒级出解。

真正有用的剪枝技巧

在递归之前的 is_valid 检查，是把"暴力枚举"变成"实用算法"的关键。归类下来常见的有五种：

约束剪枝：if not is_valid(choice): continue。永远在递归之前剪，不要在之后剪。
界剪枝：求和到目标的题里，一旦 remain < 0，或剩下所有元素加起来都凑不够 remain，立刻返回。
排序 + 提前 break：先把输入排序；当前元素超过预算时，后面所有元素都更大，直接 break。
重复元素跳过：排序之后，循环里写 if i > start and nums[i] == nums[i-1]: continue。组合总和 II 和全排列 II 的标准去重写法。
对称性剪枝：N 皇后这类问题第一行的选择天然有左右对称，可以只搜一半再镜像。

复杂度速查表

问题	时间	空间（辅助）	原因
全排列	`O(n \cdot n!)`	`O(n)`	`n!` 个叶子，每个拷贝 `O(n)`
组合总和	最坏 `O(n^{target/m})`	`O(target)`	`m = min(candidates)`；剪枝很猛
子集	`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：先 append 再判合法。 一定要在 path.append(choice) 之前做 is_valid(choice)，否则剪枝就没意义了。

坑 5：组合和排列循环起点搞混。 组合要 start 参数，排列要 used[] 数组。混淆要么生成重复，要么漏解。

坑 6：数独里反复扫"下一个空格”。 朴素写法每次调用都嵌套循环找空格，只要预处理一份 empty[] 列表就行。

常见问答（Q&A）

Q1：回溯和 DFS 的实质区别是什么？ DFS 每个节点访问一次、不改动结构；回溯在指数级多的分支之间共用同一份 path/状态，必须在回到上层时把状态恢复。回溯是"用 DFS 的方式移动”。

Q2：回溯 vs 动态规划，怎么选？ 要"所有解"用回溯；要"个数 / 最优值"且子问题重叠用 DP。有时两者都行而 DP 更快（比如统计路径数 vs 列出所有路径）。

Q3：为什么写 path[:] 而不是 path？ path 是同一个列表的引用，不拷一份的话，result 里会全是指向最终空列表的指针。

Q4：输入有重复时怎么去重？ 排序后在循环里写 if i > start and nums[i] == nums[i-1]: continue。这跳过的是同一层的相同兄弟，不会跳掉不同层里的相同元素。

Q5：组合和排列代码上差什么？ 排列用 used[]、循环每次从 0 开始；组合用 start 索引，给选出的元素固定一个标准顺序。

Q6：写对了但 TLE，从哪查？ 一是有没有在递归之前剪枝；二是合法性检查是不是 O(1)（集合 / 数组）而不是 O(n)（in path）；三是能不能排序后用 break 替掉 continue。

Q7：能改成迭代吗？ 能，把递归栈换成显式的 (path, state) 栈。递归版本几乎总是更清晰，迭代版本只在你已经撞到递归深度上限时才有用。

Q8：只要"找到一个解"怎么写？ 让递归函数返回 bool（或者直接返回解本身），一找到目标就 return True，并把这个返回值一路传上去让调用者停止迭代。

Q9：数独遇到难题就慢，怎么救？ 上 MRV：每一步都挑"当前合法候选最少"的空格先填。配合上面的 rows/cols/boxes 集合，分支因子在树底部能被砍得非常狠。

Q10：六道题学习的合理顺序？ 全排列 -> 子集 -> 组合总和 -> 单词搜索 -> N 皇后 -> 数独。每多一道题，恰好引入一个新概念（used[] -> 每节点都保存 -> start 索引 + 复用 -> 网格遍历 -> 多套约束集合 -> 提前终止 + 启发式）。

总结

回溯算法的本质就是一个节奏——选择、递归、撤销——再把约束检查嵌进去。整套技能，无非是认出模板里那四个槽位（目标、选择、合法性、状态变更），再针对眼前这道题填进去。全排列示范 used[]，子集示范"每个节点都是一个解"，组合靠 start 给选择规定标准顺序，单词搜索把模板搬到二维网格、用原地修改做"已访问"标记，N 皇后用对角线公式把约束变成 O(1) 集合查找，数独则展示了强剪枝怎么把 10^81 量级的搜索压到毫秒。

如果只能从这篇文章里记住一件事，就记这个：向下走时改的每一行，回来时都要原样改回去。 这条不变量站住了，回溯剩下的全是模板填空。

LeetCode（八）—— 回溯算法

系列导航

回溯算法到底是什么

通用模板

回溯 vs DFS：一句话区别

LeetCode 46：全排列

模板怎么填

代码实现

复杂度分析

LeetCode 39：组合总和

模板怎么填

代码实现

排序加 break 的优化

复杂度分析

LeetCode 78：子集

模板怎么填

LeetCode 79：单词搜索

LeetCode 51：N 皇后

LeetCode 37：解数独

真正有用的剪枝技巧

复杂度速查表

你大概率会踩的几个坑

常见问答（Q&A）

总结

Liked this piece?