递归与回溯

1. 概述与学习目标

1.1 什么是递归与回溯

递归（Recursion）是一种函数直接或间接调用自身的程序控制结构。John McCarthy 1960 在《Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I》（CACM 3(4):184-195, DOI:10.1145/367177.367199）中将递归作为 LISP 的核心控制结构，使递归成为函数式编程范式的基石。每个递归函数必须包含两大要素：

1. 基线条件（Base Case）：递归终止的最简情形，防止无限递归；
2. 递归条件（Recursive Case）：将原问题分解为规模更小的同构子问题并递归求解。

回溯（Backtracking）是一类系统化枚举解空间的搜索算法，以深度优先搜索（DFS）为骨架，在搜索过程中维护”当前部分解”，发现当前路径不可行时回退一步重试。Solomon W. Golomb 与 Leonard D. Baumert 1965 在《Backtrack Programming》（JACM 12(4):516-524, DOI:10.1145/321376.321386）将回溯系统化为通用组合问题求解范式。回溯算法的通用三步范式为：

1. 选择（Choose）：从候选集合中选一个元素加入当前部分解；
2. 递归（Recurse）：在新部分解上继续搜索；
3. 撤销（Unchoose）：回退状态，尝试下一个候选。

递归与回溯算法分类树：
                          递归与回溯
                              |
        ┌─────────────┬───────┴────────┬─────────────┐
      线性递归       树形递归          回溯算法       分支限界
        │              │                │              │
    ┌───┴───┐     ┌────┴────┐      ┌────┴────┐    ┌────┴────┐
   阶乘  斐波  分治递归  树遍历   子集/排列   N皇后  0-1背包   TSP
   数列  那契  归并/快排 DFS/BST  组合/数独        ILP      VRP

回溯 = 深度优先搜索 + 剪枝 + 状态重置

回溯算法与朴素 DFS 的关键区别在于剪枝（Pruning）：在递归进入分支前提前判断该分支是否可能产生可行解或最优解，不可能则直接剪去。Gaschnig 1979 CMU 博士论文《Performance measurement and analysis of certain search algorithms》系统化剪枝启发式，奠定了现代约束满足问题（CSP）求解器的基础。

一句话定义：递归 = 函数自调用 + 基线条件 + 递归条件；回溯 = DFS + 剪枝 + 状态重置；分支限界 = 回溯 + 界限剪枝；回溯通用模板为”选择-递归-撤销”三步；子集 $O(n \cdot 2^n)$、全排列 $O(n \cdot n!)$、N 皇后 $O(n!)$（剪枝后毫秒级）。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆阶乘 $O(n)$、斐波那契 $O(2^n)$ 无记忆化/$O(n)$ 记忆化、子集枚举 $O(n \cdot 2^n)$、全排列 $O(n \cdot n!)$、组合 $O(\binom{n}{k} \cdot k)$、N 皇后 $O(n!)$、数独 $O(9^{n^2})$ 最坏/$O(1)$ 摊还（约束传播）的形式化复杂度，复述回溯三要素”选择-递归-撤销”；
2. 理解 McCarthy 1960 LISP 递归系统化、Golomb-Baumert 1965 回溯法开山之作、Tarjan 1972 DFS 线性时间、Bezzel 1848 八皇后问题、Land-Doig 1960 分支限界、Knuth 2000 Dancing Links 的历史脉络，说明各算法的设计动机；
3. 应用回溯通用模板编写子集（78/90）、排列（46/47）、组合（77/39/40/216/377）、分割（131/93/784）、N 皇后（51/52）、数独（37）、括号生成（22）、单词搜索（79/212）等高频 LeetCode 题目，使用 Python/C++/Java 实现；
4. 分析递归树模型、主定理对递归复杂度的判定（$T(n) = aT(n/b) + f(n)$）、回溯通用复杂度 $O(b^d)$、剪枝的渐近改进、N 皇后位运算剪枝的实际加速效果，掌握”递归树归约、剪枝势能分析、对称性消去”三大核心论证方法；
5. 评估各回溯算法在”解空间形态（子集树 vs 排列树 vs 棋盘树）”、“剪枝强度”、“空间复杂度”、“是否需排序预处理”、“位运算可加速性”维度上的优劣，识别数独求解器、Prolog 推理引擎、SAT 求解器、Google OR-Tools、约束传播引擎的选型动机；
6. 对比子集、排列、组合、N 皇后、数独、括号生成、单词搜索、分割回文、复原 IP 在解空间结构、剪枝策略、状态表示、复杂度上的差异；
7. 创造性设计基于递归与回溯的开源项目解决方案，如数独求解器 Web App、N 皇后可视化、Prolog 解释器、SAT 求解器、Crossword 填字游戏、Sokoban 求解器、Permutation 加密器、子集和密码分析。

1.3 术语表

1.4 全景对比表

2. 历史动机与演进

2.1 时间线

timeline
    title 递归与回溯百年演进史
    1848 : Bezzel 提出八皇后问题 (Berliner Schachzeitung)
    1850 : Nauck 给出 12 个基本解 (Illustrierte Zeitung)
    1869 : 推广为 N 皇后问题
    1934 : Gödel 递归函数论 (Kleene 1936 形式化)
    1958 : Dana Scott 形式化"精确覆盖"问题
    1960 : McCarthy LISP 递归系统化 (CACM 3(4):184-195)
         : Land-Doig 分支限界 (Econometrica 28(3):497-520)
    1965 : Golomb-Baumert 回溯系统化 (JACM 12(4):516-524)
    1968 : Michie 提出记忆化 memoization (Nature 218:19-22)
    1972 : Tarjan DFS 线性时间 (SIAM J. Comp. 1(2):146-160)
         : Waltz 约束传播 (MIT AI TR-271)
         : Dijkstra《A Discipline of Programming》系统化回溯
    1975 : Bitner-Reingold 回溯实现技术 (CACM 18(11):651-656)
    1977 : Mackworth AC-3 约束传播算法
    1979 : Gaschnig 回溯启发式性能分析 (CMU-CS-79-124)
    1986 : Korf IDA* + 约束满足回溯 (AI 27:97-109)
    2000 : Knuth Dancing Links (Millennium Essay)
    2003 : Moskewicz-Sangám CDCL SAT 求解 (Chaff)
    2010 : Google OR-Tools CP-SAT 求解器
    2020 : Russell-Norvig AIMA 4th 系统化 CSP 回溯 + MRV/LCV

2.2 关键人物

2.3 关键设计决策

1. McCarthy 1958 → 1960：递归作为 LISP 核心控制结构

   McCarthy 在 1958 年 MIT 的 IBM 704 上实现 LISP 时，受 Alonzo Church 1941 $\lambda$-calculus 启发，将递归作为基本控制结构。1960 年 CACM 论文系统化 LISP 与递归。这与当时主流语言（Fortran 1957）以迭代为主形成鲜明对比，奠定了函数式编程范式。McCarthy 因此获 1971 Turing Award。

2. Golomb-Baumert 1965：回溯法系统化

   在 Golomb 之前，回溯思想散见于 Dijkstra 1959 最短路径、Walker 1960 组合优化、Bellman 1962 动态规划等。Golomb-Baumert 1965 在 JACM 论文中首次将回溯抽象为通用模板，明确”系统化枚举 + 提前剪枝”的核心思想，奠定后续 CSP、SAT、ILP 求解器的算法基础。

3. Tarjan 1972：DFS 的线性时间分析

   Tarjan 在《Depth-First Search and Linear Graph Algorithms》中证明 DFS 在 $O(V+E)$ 时间内完成，并以此为基础提出强连通分量、桥、割点、拓扑排序的线性算法。DFS 的”递归 + 栈”模式是回溯算法的执行骨架。Tarjan 因此获 1986 Turing Award。

4. Land-Doig 1960：分支限界

   Land 与 Doig 在伦敦政经学院研究整数规划时提出分支限界：将原问题分支为子问题，每个子问题用 LP 松弛求下界（最小化问题），剪去下界大于当前最优的子问题。Little-Murty-Sweeney-Karel 1963 扩展至 TSP。CLRS 第 12.4 节讨论 0-1 背包的分支限界。

5. Knuth 2000：Dancing Links

   Knuth 在 2000 年《Dancing Links》中提出 Algorithm X + 双向十字链表数据结构，用于高效求解精确覆盖问题。核心思想：利用双向链表的对称性，“覆盖列”与”恢复列”操作对称进行，实现 $O(1)$ 撤销。数独、N 皇后、Polyomino 拼图均可归约为精确覆盖。Knuth 在 TAOCP Vol. 4 Fascicle 5 进一步系统化。

6. Russell-Norvig 1995-2020：CSP 回溯 + 启发式

   AIMA 教材系统化约束满足问题（CSP）的回溯算法：MRV（Minimum Remaining Values）选择最受限变量、LCV（Least Constraining Value）选择对其他变量约束最小的值、前向检查（Forward Checking）与弧一致性（AC-3）做约束传播。这些启发式将朴素回溯的实际性能提升数个数量级，是 Google OR-Tools CP-SAT、Gecode、Chuffed 的核心。

3. 形式化定义与递归理论

3.1 递归的形式化定义

定义 3.1（递归函数）：设 $f: D \to R$ 为定义在良基集 $D$（well-founded set，任意非空子集有最小元）上的函数。$f$ 是递归函数当且仅当存在良基关系 $\prec$ 与基线函数 $g$，使得：

其中 $h$ 为组合函数，$x_1, \dots, x_k \prec x$ 为严格更小的子问题。良基性保证递归必终止。

定理 3.1（递归终止性）：若 $D$ 关于 $\prec$ 良基，则上述递归函数 $f$ 在 $D$ 上全局定义且唯一。

证明：归纳法。对任意 $x \in D$，设 $S_x = \{y \in D : y \prec x\}$。由良基性，$S_x$ 有限。假设 $f$ 在 $S_x$ 上已定义且唯一，则 $f(x) = h(x, f(x_1), \dots, f(x_k))$ 由 $h$ 唯一确定。归纳起始：$x \in B$ 时 $f(x) = g(x)$ 由 $g$ 唯一确定。$\square$

3.2 递归三要素

一个正确的递归实现必须满足：

1. 基线条件（Base Case）：存在最小情形 $B \ne \emptyset$，$f$ 在 $B$ 上直接返回；
2. 递归条件（Recursive Case）：非基线情形 $x \notin B$ 时，递归调用 $f(x_i)$ 其中 $x_i \prec x$；
3. 状态收缩（Progress）：每次递归调用使子问题严格”更小”（关于 $\prec$），保证收敛到基线。

反例 1（无基线）：def f(n): return f(n-1) — 无限递归。

反例 2（无收缩）：def f(n): return f(n) — 无限递归。

正例：阶乘 factorial(n)：

• 基线：$n \le 1$ 时返回 1；
• 递归：$n \ge 2$ 时返回 $n \cdot \text{factorial}(n-1)$；
• 收缩：$n \to n-1$ 严格递减。

3.3 递归树模型与主定理回顾

递归树（Recursion Tree）是分析递归复杂度的可视化工具。对于递推：

$T(n) = a \cdot T(n/b) + f(n)$

递归树第 $i$ 层有 $a^i$ 个节点，每个节点规模 $n/b^i$，每节点代价 $f(n/b^i)$。叶节点（基线）在 $i = \log_b n$ 层，共 $a^{\log_b n} = n^{\log_b a}$ 个叶节点。

主定理（Master Theorem, Bentley-Haken-Saxe 1980）：分三种情况：

1. 情况 1：若 $f(n) = O(n^{\log_b a - \epsilon})$（$\epsilon > 0$），则 $T(n) = \Theta(n^{\log_b a})$；
2. 情况 2：若 $f(n) = \Theta(n^{\log_b a} \log^k n)$（$k \ge 0$），则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$；
3. 情况 3：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且满足正则条件 $a f(n/b) \le c f(n)$（$c < 1$），则 $T(n) = \Theta(f(n))$。

应用举例：

• 阶乘 factorial(n)：$T(n) = T(n-1) + O(1)$，主定理不适用（非 $n/b$ 分裂），但易得 $T(n) = O(n)$；
• 斐波那契（无记忆化）fib(n)：$T(n) = T(n-1) + T(n-2) + O(1)$，解为 $O(\phi^n) = O(1.618^n)$，其中 $\phi = (1+\sqrt{5})/2$ 为黄金比；
• 二分递归（如归并排序）：$T(n) = 2T(n/2) + O(n)$，主定理情况 2 得 $O(n \log n)$；
• 回溯（子集枚举）：$T(n) = 2T(n-1) + O(n)$，解为 $O(n \cdot 2^n)$。

3.4 尾递归与尾调用优化

定义 3.2（尾递归）：递归调用是函数的最后一步操作（无后续计算）。

# 非尾递归：递归后有乘法
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)  # 递归返回后还要乘 n

# 尾递归版本：用累加器参数
def factorial_tail(n, acc=1):
    if n <= 1: return acc
    return factorial_tail(n - 1, n * acc)  # 递归是最后操作

尾调用优化（Tail Call Optimization, TCO）：Guy Steele 1977 在 MIT AI Memo 441《Debunking the “Expensive Procedure Call” Myth》系统化。支持 TCO 的编译器将尾递归编译为循环，空间复杂度 $O(n) \to O(1)$。

Python 替代方案：增大递归限制 sys.setrecursionlimit 或显式栈迭代。

3.5 记忆化递归

Donald Michie 1968 在《Memo Functions and Machine Learning》（Nature 218:19-22）提出 memoization，源自 memorandum（备忘录）。记忆化通过缓存子问题结果避免重复计算。

经典对比：斐波那契数列

from functools import lru_cache

# 朴素递归：O(2^n) 指数级
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# 记忆化递归：O(n)
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

# 自底向上 DP：O(n) 时间 O(1) 空间
def fib_dp(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

fib_naive(40) 需约 $2^{40} \approx 10^{12}$ 次调用，实际运行数十秒；fib_memo(40) 仅 41 次调用，毫秒级完成。

3.6 回溯算法的形式化定义

定义 3.3（解空间）：组合问题 $\mathcal{P}$ 的解空间 $\mathcal{S}$ 为所有候选解的集合。$\mathcal{S}$ 通常组织为 $k$-叉树：

• 根节点：空部分解 $\langle \rangle$；
• 内部节点：长度 $i < n$ 的部分解 $\langle a_1, a_2, \dots, a_i \rangle$；
• 叶节点：长度 $n$ 的完整解 $\langle a_1, \dots, a_n \rangle$。

定义 3.4（剪枝函数）：剪枝函数 $\text{prune}: \mathcal{S}_{\text{partial}} \to \{0, 1\}$ 接受部分解，返回 1 表示该分支不可能产生可行/最优解，应剪去。

回溯算法骨架：

Backtrack(P, partial_solution):
    if terminal(partial_solution):
        record(partial_solution)
        return
    for candidate in candidates(P, partial_solution):
        if not prune(partial_solution + [candidate]):
            choose(candidate)
            Backtrack(P, partial_solution + [candidate])
            unchoose(candidate)  # 状态重置

复杂度分析：

• 时间：$O(b^d)$，其中 $b$ 为分支因子（每层平均候选数）、$d$ 为递归深度；
• 空间：$O(d)$（递归栈）+ $O(\text{solution size})$（部分解存储）。

3.7 回溯的三大解空间形态

子集树示意（$n = 3$）：

                    {}
                /        \
              {1}         {}
            /    \       /    \
         {1,2}  {1}    {2}    {}
         /  \   / \    / \    / \
     {1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}(叶节点)

排列树示意（$n = 3$）：

                  []
            /     |     \
          [1]    [2]    [3]
         /  \   /  \   /  \
      [1,2][1,3][2,1][2,3][3,1][3,2]
        |    |    |    |    |    |
     [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

4. 递归基础与经典实现

4.1 阶乘：递归入门

def factorial(n: int) -> int:
    """阶乘递归实现：T(n) = O(n), S(n) = O(n)"""
    # 基线条件
    if n <= 1:
        return 1
    # 递归条件：将 n! 分解为 n * (n-1)!
    return n * factorial(n - 1)

# 执行过程：factorial(4) = 4 * factorial(3)
#                          = 4 * 3 * factorial(2)
#                          = 4 * 3 * 2 * factorial(1)
#                          = 4 * 3 * 2 * 1 = 24

#include <cstdint>
// C++ 尾递归版本，编译器 -O2 可优化为循环
std::int64_t factorial_tail(int n, std::int64_t acc = 1) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // 尾递归
}

4.2 斐波那契：树形递归与记忆化

from functools import lru_cache

def fib_naive(n: int) -> int:
    """朴素递归：T(n) = O(φ^n), φ ≈ 1.618"""
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    """记忆化递归：T(n) = O(n), S(n) = O(n)"""
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

def fib_dp(n: int) -> int:
    """自底向上 DP：T(n) = O(n), S(n) = O(1)"""
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 朴素递归调用次数（C(n) = C(n-1) + C(n-2) + 1）：
# n=10: 177 次；n=20: 21891 次；n=30: 2692537 次；n=40: 331160281 次

复杂度推导：

朴素递归调用次数 $C(n) = C(n-1) + C(n-2) + 1$，其特征方程 $x^2 = x + 1$ 的解为黄金比 $\phi = (1+\sqrt{5})/2 \approx 1.618$，故 $C(n) = \Theta(\phi^n)$。

记忆化后每 $n$ 只计算一次，共 $n$ 次递归调用，每次 $O(1)$，总计 $O(n)$。

4.3 递归与迭代的转换

定理 4.1：任何递归都可转换为等价的迭代（用显式栈模拟调用栈）。

# 递归版二叉树中序遍历
def inorder_recursive(root):
    if not root: return
    inorder_recursive(root.left)
    process(root)
    inorder_recursive(root.right)

# 迭代版（显式栈）
def inorder_iterative(root):
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        process(node)
        node = node.right

应用场景：

• 深度过大时（Python 默认 1000 限制）；
• 性能敏感场景（避免函数调用开销）；
• 需要精确控制栈状态时。

4.4 递归复杂度分类

5. 回溯通用模板与子集问题

5.1 回溯通用模板（Stanford CS106B 风格）

def backtrack(path, choices):
    """
    回溯通用模板：
    - path: 当前部分解
    - choices: 当前可做的候选选择
    """
    # 终止条件：达到目标
    if satisfies_end_condition(path):
        result.append(path[:])  # 注意：必须拷贝
        return

    # 遍历候选
    for choice in candidates(choices):
        # 1. 选择
        path.append(choice)
        new_choices = update_choices(choices, choice)

        # 2. 递归
        backtrack(path, new_choices)

        # 3. 撤销（状态重置）
        path.pop()

5.2 子集问题（LeetCode 78, 90）

子集树：$n$ 个元素的子集数为 $2^n$，每个元素”选/不选”。

def subsets(nums: list[int]) -> list[list[int]]:
    """LeetCode 78: 子集（无重复元素）
    解空间：子集树 2^n
    时间：O(n * 2^n)  空间：O(n)
    """
    result = []

    def backtrack(start: int, path: list[int]) -> None:
        # 收集所有节点（不仅是叶子），每个节点对应一个子集
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])           # 选择
            backtrack(i + 1, path)         # 递归（i+1 避免重复）
            path.pop()                     # 撤销

    backtrack(0, [])
    return result

# 示例
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

含重复元素的子集（LeetCode 90）：

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """LeetCode 90: 子集 II（含重复元素）
    关键：先排序，同层跳过相邻重复
    """
    nums.sort()  # 排序是去重的前提
    result = []

    def backtrack(start: int, path: list[int]) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            # 剪枝：同层跳过相邻重复（i > start 保证不同层可重选）
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print(subsets_with_dup([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]]

位运算法（仅适用于 $n \le 20$）：

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    """位掩码枚举：用 0..2^n-1 的二进制表示选/不选"""
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

5.3 组合问题（LeetCode 77, 39, 40, 216, 377）

组合 C(n, k)：

def combine(n: int, k: int) -> list[list[int]]:
    """LeetCode 77: 从 1..n 中选 k 个数的所有组合"""
    result = []

    def backtrack(start: int, path: list[int]) -> None:
        if len(path) == k:
            result.append(path[:])
            return

        # 边界剪枝：剩余元素不足时提前终止
        # 还需 k - len(path) 个，剩余范围 [start, n]
        # 上界 = n - (k - len(path)) + 1
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))
# [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

组合总和（可重复选）：

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """LeetCode 39: 组合总和（可重复选取）"""
    result = []

    def backtrack(start: int, path: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return  # 边界剪枝

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            # 注意是 i 不是 i+1，允许重复选同一元素
            backtrack(i, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]

组合总和 II（每个数只能用一次，含重复元素）：

def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    """LeetCode 40: 组合总和 II（每个数只能用一次，含重复）"""
    candidates.sort()  # 排序是剪枝与去重的前提
    result = []

    def backtrack(start: int, path: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # 剪枝 1：当前元素超过 remaining，后面更大元素必然也超
            if candidates[i] > remaining:
                break
            # 剪枝 2：同层跳过相邻重复
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])  # i+1 不重复
            path.pop()

    backtrack(0, [], target)
    return result

print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]

5.4 排列问题（LeetCode 46, 47）

全排列（无重复）：

def permute(nums: list[int]) -> list[list[int]]:
    """LeetCode 46: 全排列（无重复）
    解空间：排列树 n!
    时间：O(n * n!)  空间：O(n)
    """
    result = []

    def backtrack(path: list[int], used: list[bool]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

print(permute([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

全排列 II（含重复）：

def permute_unique(nums: list[int]) -> list[list[int]]:
    """LeetCode 47: 全排列 II（含重复）"""
    nums.sort()
    result = []

    def backtrack(path: list[int], used: list[bool]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            # 剪枝：同层跳过重复，且前一个未使用（保证相同元素按序选）
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

print(permute_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]]

为何 not used[i-1] 的判断条件：保证相同元素按顺序选择，避免重复排列。若 used[i-1] = True（前一相同元素在本路径中已选），则当前元素 nums[i] 可选（不同层）；若 used[i-1] = False（前一相同元素在更早层选过又撤销，即同层），则跳过当前元素。

5.5 括号生成（LeetCode 22）

def generate_parenthesis(n: int) -> list[str]:
    """LeetCode 22: 生成 n 对合法括号的所有组合
    解空间：Catalan 树 C_n = C(2n,n)/(n+1)
    时间：O(4^n / sqrt(n))  空间：O(n)
    """
    result = []

    def backtrack(s: str, left: int, right: int) -> None:
        # 终止：用了 n 个左括号 n 个右括号
        if len(s) == 2 * n:
            result.append(s)
            return
        # 可加左括号：未用完
        if left < n:
            backtrack(s + '(', left + 1, right)
        # 可加右括号：右比左少（保证合法）
        if right < left:
            backtrack(s + ')', left, right + 1)

    backtrack('', 0, 0)
    return result

print(generate_parenthesis(3))
# ["((()))","(()())","(())()","()(())","()()()"]

复杂度：第 $n$ 个 Catalan 数 $C_n = \frac{1}{n+1}\binom{2n}{n} \approx \frac{4^n}{n^{3/2}\sqrt{\pi}}$。

6. N 皇后问题（Bezzel 1848）

6.1 历史背景

1848 年 9 月，德国慕尼黑国际象棋手 Max Bezzel 在《Berliner Schachzeitung》（柏林国际象棋杂志）3:363 提出”八皇后问题”：在 $8 \times 8$ 棋盘上放置 8 个皇后，使任意两个皇后互不攻击（同行、同列、同对角线不冲突）。

1850 年 6 月，德国数学家 Franz Nauck 在《Illustrierte Zeitung》14:351-352 给出全部 12 个基本解（除去旋转对称共 92 个解）。Nauck 同时将问题推广至 $n$ 皇后。

1869 年，法国数学家 Édouard Lucas 在《Récréations Mathématiques》系统化研究 N 皇后并给出递推关系。

解的数量（OEIS A000170）：

6.2 标准回溯实现

def solve_n_queens(n: int) -> list[list[str]]:
    """LeetCode 51: N 皇后问题
    解空间：棋盘树，剪枝后 n! 个叶节点
    时间：O(n!) 实际毫秒级（剪枝强力）
    空间：O(n)
    """
    result = []

    def is_valid(board: list[list[str]], row: int, col: int) -> bool:
        # 检查同列（上方行）
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        # 检查左上对角线
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1; j -= 1
        # 检查右上对角线
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1; j += 1
        return True

    def backtrack(row: int, board: list[list[str]]) -> None:
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if not is_valid(board, row, col):
                continue  # 剪枝：列/对角线冲突
            board[row][col] = 'Q'    # 选择
            backtrack(row + 1, board)
            board[row][col] = '.'    # 撤销

    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, board)
    return result

# 验证 8 皇后
solutions = solve_n_queens(8)
print(f"8 皇后解数: {len(solutions)}")  # 92

6.3 集合加速版

用三个集合 $O(1)$ 判定冲突，避免 is_valid 的 $O(n)$ 线性扫描：

def solve_n_queens_set(n: int) -> list[list[str]]:
    """集合加速版：用 cols/diagonals/anti_diagonals 集合 O(1) 判定"""
    result = []
    cols = set()
    diagonals = set()       # 主对角线 row - col
    anti_diagonals = set()  # 副对角线 row + col

    def backtrack(row: int, board: list[list[str]]) -> 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 diagonals or (row + col) in anti_diagonals:
                continue  # 冲突剪枝
            # 选择
            cols.add(col)
            diagonals.add(row - col)
            anti_diagonals.add(row + col)
            board[row][col] = 'Q'

            backtrack(row + 1, board)

            # 撤销
            cols.remove(col)
            diagonals.remove(row - col)
            anti_diagonals.remove(row + col)
            board[row][col] = '.'

    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, board)
    return result

6.4 位运算终极优化

利用位掩码将列与对角线状态压缩到整数，常数级判定与迭代：

def total_n_queens_bit(n: int) -> int:
    """LeetCode 52: N 皇后 II（位运算版）
    关键思想：
    - cols: 已占用的列（bit=1 表示冲突）
    - hills: 已占用的主对角线 row-col
    - dales: 已占用的副对角线 row+col
    - available: 当前可放置的列（bit=1）
    """
    count = 0

    def backtrack(row: int, cols: int, hills: int, dales: int) -> None:
        nonlocal count
        if row == n:
            count += 1
            return
        # 可放置的列：(~(cols | hills | dales)) & ((1 << n) - 1)
        available = ~(cols | hills | dales) & ((1 << n) - 1)
        while available:
            # 取最低位的 1 作为放置位置
            p = available & -available
            available ^= p  # 清除该位
            # 下一行：cols | p（占用此列）
            #          hills | p 下一行此列与下一列形成主对角线，左移
            #          dales | p 下一行此列与上一列形成副对角线，右移
            backtrack(row + 1,
                      cols | p,
                      (hills | p) << 1,
                      (dales | p) >> 1)

    backtrack(0, 0, 0, 0)
    return count

# 性能对比（n=15）：
# 朴素版 is_valid O(n):  ~30s
# 集合版 O(1):          ~3s
# 位运算版:             ~0.3s（10 倍加速）

位运算原理：

• cols | hills | dales：合并所有冲突位；
• ~(...)：取反得到可放置位（高位需 mask）；
• & ((1<<n)-1)：保留低 $n$ 位；
• p & -p：取最低位的 1（Brian Kernighan 技巧）；
• (hills | p) << 1：主对角线下一行左移一位（因下一行此列影响下一列）；
• (dales | p) >> 1：副对角线下一行右移一位。

7. 数独求解器（LeetCode 37）

7.1 数独简介

数独由美国建筑师 Howard Garns 1979 年在 Dell Magazines《Math Problems and Logic Puzzles》首次发表，名为”Number Place”。1984 年日本 Nikoli 出版社引入并命名为”数独”（Su = 数字，Doku = 单独）。2004 年 The Times 推广至全球。

规则：在 $9 \times 9$ 网格中填入 1-9 数字，使每行、每列、每个 $3 \times 3$ 宫格内 1-9 各出现一次。

7.2 朴素回溯实现

def solve_sudoku(board: list[list[str]]) -> None:
    """LeetCode 37: 解数独（原地修改）
    时间：最坏 O(9^(n^2))，实际毫秒级（约束传播）
    """
    def is_valid(board, row, col, num):
        # 检查行
        for j in range(9):
            if board[row][j] == num:
                return False
        # 检查列
        for i in range(9):
            if board[i][col] == num:
                return False
        # 检查 3x3 宫
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        return True

    def backtrack() -> bool:
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue
                for num in '123456789':
                    if is_valid(board, i, j, num):
                        board[i][j] = num  # 选择
                        if backtrack():
                            return True
                        board[i][j] = '.'  # 撤销
                return False  # 9 个数字都不行，回溯
        return True  # 全部填完

    backtrack()

7.3 约束传播加速

用三个二维数组缓存行/列/宫已用数字，将 is_valid 从 $O(n)$ 降到 $O(1)$：

def solve_sudoku_fast(board: list[list[str]]) -> None:
    """约束传播加速版：行/列/宫状态缓存"""
    rows = [[False] * 9 for _ in range(9)]
    cols = [[False] * 9 for _ in range(9)]
    boxes = [[False] * 9 for _ in range(9)]

    # 初始化已填数字
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                num = int(board[i][j]) - 1
                rows[i][num] = True
                cols[j][num] = True
                box_idx = (i // 3) * 3 + j // 3
                boxes[box_idx][num] = True

    def backtrack() -> bool:
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue
                box_idx = (i // 3) * 3 + j // 3
                for num in range(9):
                    if not rows[i][num] and not cols[j][num] and not boxes[box_idx][num]:
                        # 选择
                        board[i][j] = str(num + 1)
                        rows[i][num] = cols[j][num] = boxes[box_idx][num] = True
                        if backtrack():
                            return True
                        # 撤销
                        board[i][j] = '.'
                        rows[i][num] = cols[j][num] = boxes[box_idx][num] = False
                return False
        return True

    backtrack()

7.4 MRV 启发式（Russell-Norvig AIMA）

MRV（Minimum Remaining Values）：每次选择”剩余可填数字最少”的空格优先填，大幅减少分支因子：

def solve_sudoku_mrv(board: list[list[str]]) -> None:
    """MRV 启发式：选最少剩余值的空格优先填"""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                num = int(board[i][j])
                rows[i].add(num); cols[j].add(num)
                boxes[(i // 3) * 3 + j // 3].add(num)

    def find_mrv_cell():
        """找剩余可填数字最少的空格"""
        best = None
        best_count = 10
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue
                box_idx = (i // 3) * 3 + j // 3
                used = rows[i] | cols[j] | boxes[box_idx]
                cnt = 9 - len(used)
                if cnt < best_count:
                    best_count = cnt
                    best = (i, j)
                    if cnt == 1:
                        return best  # 最优情况，提前返回
        return best

    def backtrack() -> bool:
        cell = find_mrv_cell()
        if cell is None:
            return True  # 全部填完
        i, j = cell
        box_idx = (i // 3) * 3 + j // 3
        for num in range(1, 10):
            if num not in rows[i] and num not in cols[j] and num not in boxes[box_idx]:
                board[i][j] = str(num)
                rows[i].add(num); cols[j].add(num); boxes[box_idx].add(num)
                if backtrack():
                    return True
                board[i][j] = '.'
                rows[i].discard(num); cols[j].discard(num); boxes[box_idx].discard(num)
        return False

    backtrack()

8. 分割问题与单词搜索

8.1 分割回文串（LeetCode 131）

def partition(s: str) -> list[list[str]]:
    """LeetCode 131: 分割回文串
    解空间：切分树（在每个位置切/不切）
    时间：O(n * 2^n)  空间：O(n)
    """
    result = []
    n = len(s)

    def is_palindrome(sub: str) -> bool:
        return sub == sub[::-1]

    def backtrack(start: int, path: list[str]) -> None:
        if start == n:
            result.append(path[:])
            return
        for end in range(start + 1, n + 1):
            sub = s[start:end]
            if is_palindrome(sub):  # 剪枝：当前段必须回文
                path.append(sub)
                backtrack(end, path)
                path.pop()

    backtrack(0, [])
    return result

print(partition("aab"))
# [["a","a","b"],["aa","b"]]

DP 预处理优化：用 $O(n^2)$ 预计算 dp[i][j] 表示 s[i:j+1] 是否回文：

def partition_dp(s: str) -> list[list[str]]:
    """DP 预处理回文判断，回溯过程 O(1) 判定"""
    n = len(s)
    # dp[i][j] = True 表示 s[i..j] 是回文
    dp = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
                dp[i][j] = True

    result = []

    def backtrack(start: int, path: list[str]) -> None:
        if start == n:
            result.append(path[:])
            return
        for end in range(start, n):
            if dp[start][end]:
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result

8.2 复原 IP 地址（LeetCode 93）

def restore_ip_addresses(s: str) -> list[str]:
    """LeetCode 93: 复原 IP 地址
    解空间：4 段切分树
    时间：O(3^4) = O(81)  空间：O(4)
    """
    result = []
    n = len(s)

    def backtrack(start: int, path: list[str]) -> None:
        # 终止：4 段且用完所有字符
        if len(path) == 4:
            if start == n:
                result.append('.'.join(path))
            return
        # 剪枝：剩余字符过多或过少
        remaining = n - start
        if remaining < (4 - len(path)) or remaining > 3 * (4 - len(path)):
            return

        for length in range(1, 4):
            if start + length > n:
                break
            segment = s[start:start + length]
            # 剪枝：前导 0、数值超 255
            if len(segment) > 1 and segment[0] == '0':
                continue
            if int(segment) > 255:
                continue
            path.append(segment)
            backtrack(start + length, path)
            path.pop()

    backtrack(0, [])
    return result

print(restore_ip_addresses("25525511135"))
# ["255.255.11.135","255.255.111.35"]

8.3 单词搜索（LeetCode 79）

def exist(board: list[list[str]], word: str) -> bool:
    """LeetCode 79: 单词搜索
    解空间：字符网格 DFS
    时间：O(mn * 4^L)  L 为单词长度
    空间：O(L) 递归深度
    """
    m, n = len(board), len(board[0])

    def backtrack(i: int, j: int, k: int) -> bool:
        if k == len(word):
            return True
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
            return False
        # 临时标记访问（原地修改避免 visited 矩阵）
        temp, board[i][j] = board[i][j], '#'
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if backtrack(i + di, j + dj, k + 1):
                board[i][j] = temp  # 恢复（撤销）
                return True
        board[i][j] = temp  # 撤销
        return False

    for i in range(m):
        for j in range(n):
            if backtrack(i, j, 0):
                return True
    return False

8.4 单词搜索 II（LeetCode 212，Trie + 回溯）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # 叶节点存储完整单词

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    """LeetCode 212: 单词搜索 II
    关键优化：Trie 剪枝，避免重复搜索
    时间：O(mn * 4^L)  L 为最长单词长度
    """
    # 构建 Trie
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w

    m, n = len(board), len(board[0])
    result = []

    def backtrack(i: int, j: int, node: TrieNode) -> None:
        ch = board[i][j]
        if ch not in node.children:
            return
        next_node = node.children[ch]
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # 防重复

        board[i][j] = '#'  # 标记访问
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
                backtrack(ni, nj, next_node)
        board[i][j] = ch  # 撤销

    for i in range(m):
        for j in range(n):
            backtrack(i, j, root)
    return result

9. 分支限界与 Dancing Links

9.1 分支限界（Land-Doig 1960）

分支限界（Branch and Bound）由 Ailsa Land 与 Alison Doig 1960 在《An automatic method of solving discrete programming problems》（Econometrica 28(3):497-520, DOI:10.2307/1910129）提出。核心思想：

1. 分支（Branch）：将原问题分解为子问题（如 0-1 背包中”取物品 $i$“与”不取”）；
2. 限界（Bound）：对每个子问题求松弛问题的界（如 LP 松弛），剪去界劣于当前最优的子问题；
3. 搜索：用 BFS（最佳优先）或 DFS 优先扩展界最优的子问题。

0-1 背包分支限界示例：

import heapq

def knapsack_branch_bound(values, weights, capacity):
    """0-1 背包分支限界（最佳优先 + LP 上界）
    返回最大价值
    """
    n = len(values)
    # 按单位价值降序排序
    items = sorted(range(n), key=lambda i: values[i] / weights[i], reverse=True)

    def bound(i, current_weight, current_value):
        """LP 松弛上界：剩余物品可部分取"""
        if current_weight >= capacity:
            return 0
        bound_value = current_value
        bound_weight = current_weight
        for j in range(i, n):
            idx = items[j]
            if bound_weight + weights[idx] <= capacity:
                bound_weight += weights[idx]
                bound_value += values[idx]
            else:
                # 部分取
                bound_value += (capacity - bound_weight) * values[idx] / weights[idx]
                break
        return bound_value

    max_value = 0
    # 优先队列：(-bound, level, current_weight, current_value)
    pq = [(-bound(0, 0, 0), 0, 0, 0)]

    while pq:
        _, level, cw, cv = heapq.heappop(pq)
        if level >= n:
            continue
        idx = items[level]
        # 取物品
        if cw + weights[idx] <= capacity:
            new_value = cv + values[idx]
            if new_value > max_value:
                max_value = new_value
            new_bound = bound(level + 1, cw + weights[idx], new_value)
            if new_bound > max_value:
                heapq.heappush(pq, (-new_bound, level + 1, cw + weights[idx], new_value))
        # 不取物品
        new_bound = bound(level + 1, cw, cv)
        if new_bound > max_value:
            heapq.heappush(pq, (-new_bound, level + 1, cw, cv))

    return max_value

# 示例
print(knapsack_branch_bound([60, 100, 120], [10, 20, 30], 50))  # 220

与回溯的关键区别：

• 回溯用 DFS 任意顺序搜索，靠可行性剪枝；
• 分支限界用 BFS/最佳优先 + 界限剪枝，保证找到最优解时已剪去所有次优分支；
• 分支限界常用于最优化问题（ILP/TSP/VRP），回溯常用于枚举/决策问题。

9.2 精确覆盖与 Algorithm X

精确覆盖（Exact Cover）由 Dana Scott 1958 形式化：给定 0-1 矩阵 $A$，选若干行使每列恰好一个 1。

Algorithm X（Knuth 2000）：

1. 若 A 为空，返回成功
2. 选列 c（1 最少）
3. 对每个行 r 满足 A[r][c] = 1:
   a. 将 r 加入部分解
   b. 覆盖 r 中所有 1 所在列（删除这些列及含这些列的行）
   c. 递归 Algorithm X
   d. 撤销覆盖（恢复行与列）

9.3 Dancing Links 实现

Knuth 2000 在《Dancing Links》中提出双向十字链表实现 Algorithm X 的 $O(1)$ 撤销：

class DLXNode:
    __slots__ = ['left', 'right', 'up', 'down', 'col', 'row', 'size', 'name']
    def __init__(self):
        self.left = self.right = self.up = self.down = self
        self.col = self  # 列头指向自己
        self.row = -1
        self.size = 0    # 列大小
        self.name = None

class DancingLinks:
    """Knuth Dancing Links 精确覆盖求解器"""
    def __init__(self):
        self.header = DLXNode()  # 全局列头
        self.col_headers = []

    def add_column(self, name):
        col = DLXNode()
        col.name = name
        col.col = col
        # 插入到 header 左侧
        col.left = self.header.left
        col.right = self.header
        self.header.left.right = col
        self.header.left = col
        self.col_headers.append(col)
        return col

    def add_row(self, row_id, col_indices):
        """添加一行：在指定列插入节点"""
        first = None
        for ci in col_indices:
            col = self.col_headers[ci]
            node = DLXNode()
            node.row = row_id
            node.col = col
            # 上下插入到列尾
            node.up = col.up
            node.down = col
            col.up.down = node
            col.up = node
            col.size += 1
            # 左右插入到行尾
            if first is None:
                first = node
                node.left = node.right = node
            else:
                node.left = first.left
                node.right = first
                first.left.right = node
                first.left = node

    def cover(self, col):
        """覆盖列 col：删除该列及含该列的所有行"""
        col.right.left = col.left
        col.left.right = col.right
        i = col.down
        while i != col:
            j = i.right
            while j != i:
                j.down.up = j.up
                j.up.down = j.down
                j.col.size -= 1
                j = j.right
            i = i.down

    def uncover(self, col):
        """撤销覆盖：与 cover 严格对称（逆序恢复）"""
        i = col.up
        while i != col:
            j = i.left
            while j != i:
                j.col.size += 1
                j.down.up = j
                j.up.down = j
                j = j.left
            i = i.up
        col.right.left = col
        col.left.right = col

    def search(self, solution):
        """Algorithm X 主体"""
        if self.header.right == self.header:
            return True  # 全部列已覆盖
        # 选 size 最小的列（启发式）
        col = min(iter_col_headers(self.header), key=lambda c: c.size)
        self.cover(col)
        i = col.down
        while i != col:
            solution.append(i.row)
            j = i.right
            while j != i:
                self.cover(j.col)
                j = j.right
            if self.search(solution):
                return True
            # 回溯
            j = i.left
            while j != i:
                self.uncover(j.col)
                j = j.left
            solution.pop()
            i = i.down
        self.uncover(col)
        return False

def iter_col_headers(header):
    cur = header.right
    while cur != header:
        yield cur
        cur = cur.right

应用：

• 数独：将 $9 \times 9$ 数独归约为 4 列约束（行-数字、列-数字、宫-数字、位置），共 324 列、729 行；
• N 皇后：将列、主对角线、副对角线约束归约为 $6n - 2$ 列、$n^2$ 行；
• Polyomino 拼图：将位置-方块约束归约为精确覆盖。

10. 经典应用案例（LeetCode 高频题）

10.1 LeetCode 131: 分割回文串

见 8.1 节。

10.2 LeetCode 17: 电话号码的字母组合

def letter_combinations(digits: str) -> list[str]:
    """LeetCode 17: 电话号码字母组合
    时间：O(4^n)  空间：O(n)
    """
    if not digits:
        return []
    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []

    def backtrack(idx: int, path: list[str]) -> None:
        if idx == len(digits):
            result.append(''.join(path))
            return
        for ch in phone[digits[idx]]:
            path.append(ch)
            backtrack(idx + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print(letter_combinations("23"))
# ["ad","ae","af","bd","be","bf","cd","ce","cf"]

10.3 LeetCode 39/40/216/377: 组合总和系列

见 5.3 节。

10.4 LeetCode 47/51/37: 全排列/N 皇后/数独

见 5.4、6.2、7.2 节。

10.5 LeetCode 79/212: 单词搜索 I/II

见 8.3、8.4 节。

10.6 LeetCode 491: 递增子序列

def find_subsequences(nums: list[int]) -> list[list[int]]:
    """LeetCode 491: 非递减子序列（不排序的去重）"""
    result = []

    def backtrack(start: int, path: list[int]) -> None:
        if len(path) >= 2:
            result.append(path[:])
        # 同层去重（不排序）
        used = set()
        for i in range(start, len(nums)):
            if nums[i] in used:
                continue
            if path and nums[i] < path[-1]:
                continue  # 剪枝：非递减
            used.add(nums[i])
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

10.7 LeetCode 90: 子集 II

见 5.2 节。

10.8 LeetCode 401: 二进制手表

def read_binary_watch(turned_on: int) -> list[str]:
    """LeetCode 401: 二进制手表（n 个 LED 亮）
    解空间：10 位中选 turned_on 位
    """
    result = []
    # 10 位中前 4 位为小时，后 6 位为分钟
    for h in range(12):
        for m in range(60):
            if bin(h).count('1') + bin(m).count('1') == turned_on:
                result.append(f"{h}:{m:02d}")
    return result

11. 工程实践与并行化

11.1 迭代化回溯（避免递归栈溢出）

def subsets_iterative(nums: list[int]) -> list[list[int]]:
    """显式栈迭代版子集枚举"""
    result = []
    n = len(nums)
    # 栈元素：(start, path)
    stack = [(0, [])]
    while stack:
        start, path = stack.pop()
        result.append(path)
        for i in range(n - 1, start - 1, -1):  # 逆序入栈保证顺序
            stack.append((i + 1, path + [nums[i]]))
    return result

11.2 并行回溯（任务划分）

from concurrent.futures import ProcessPoolExecutor

def n_queens_parallel(n: int) -> int:
    """并行 N 皇后：按第一行列划分任务"""
    def solve_partial(first_col: int) -> int:
        """固定第一行皇后在 first_col 列，求剩余解数"""
        count = 0
        cols = {first_col}
        diag = {first_col}      # row - col = 0 - first_col
        anti = {first_col}      # row + col = 0 + first_col

        def backtrack(row: int):
            nonlocal count
            if row == n:
                count += 1
                return
            for col in range(n):
                if col in cols or (row - col) in diag or (row + col) in anti:
                    continue
                cols.add(col); diag.add(row - col); anti.add(row + col)
                backtrack(row + 1)
                cols.discard(col); diag.discard(row - col); anti.discard(row + col)

        backtrack(1)
        return count

    with ProcessPoolExecutor(max_workers=n) as executor:
        results = list(executor.map(solve_partial, range(n)))
    return sum(results)

# 16 皇后：单线程约 30s，16 线程约 3s

11.3 工业级优化技巧

1. 位运算状态压缩：N 皇后、子集枚举等用位掩码替代布尔数组；
2. 预排序：组合/排列去重、剪枝依赖排序后相邻性；
3. 约束传播预处理：数独的”裸单""隐单”预填，显著减少回溯分支；
4. 启发式选择：MRV（最少剩余值）、LCV（最少约束值）启发式；
5. 迭代加深（IDDFS）：当解深度未知时，逐层加深避免深度陷阱；
6. 记忆化避免重复子问题：与 DP 结合（如 294/494 等记忆化回溯）；
7. 对称性消去：N 皇后利用棋盘对称性将搜索空间减至 1/8；
8. 任务并行：按第一层划分任务，多进程/多线程并行。

11.4 工业级回溯框架

• Google OR-Tools CP-SAT：现代化 CP 求解器，集成约束传播、回溯、CDCL；
• Chuffed：lazy clause generation 回溯求解器；
• Gecode：C++ 并行回溯框架；
• MiniZinc/Gurobi/CPLEX：建模语言 + 商用 ILP/CP 求解器；
• Prolog：内置回溯执行模型，统一逻辑变量与约束。

12. 常见陷阱与调试

12.1 路径拷贝遗漏

# 错误：直接引用 path，后续修改会污染已保存结果
result.append(path)

# 正确：拷贝当前快照
result.append(path[:])
result.append(path.copy())
result.append(list(path))
result.append(''.join(path))  # 字符串路径

12.2 同层去重 vs 同路径去重

# LeetCode 47 全排列 II 去重
# 正确条件：i > 0 and nums[i] == nums[i-1] and not used[i-1]
# 解释：
# - used[i-1] = True：前一相同元素在当前路径中已选，则 nums[i] 是后续层，可选
# - used[i-1] = False：前一相同元素同层已撤销，则 nums[i] 同层重复，跳过

# 错误条件：not used[i-1] 改为 used[i-1]
# 会导致某些合法排列被错误剪掉

12.3 递归深度溢出

import sys
sys.setrecursionlimit(10000)  # 临时增大限制

# 更好：转换为迭代
def dfs_iterative(root):
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node is None:
            continue
        if visited:
            process(node)
        else:
            # 后序：右-左-根
            if node.right: stack.append((node.right, False))
            if node.left: stack.append((node.left, False))
            stack.append((node, True))

12.4 剪枝条件错误

# 组合总和剪枝：必须先排序才能 break
def combination_sum2_wrong(candidates, target):
    candidates.sort()  # 必须先排序
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:]); return
        for i in range(start, len(candidates)):
            # 错误：用 continue 而非 break
            if candidates[i] > remaining:
                continue  # 应改为 break（已排序，后续更大）
            # ...

12.5 状态重置遗漏

# N 皇后位运算版常见错误：忘记左移右移
def backtrack(row, cols, hills, dales):
    # ...
    p = available & -available
    backtrack(row + 1,
              cols | p,
              (hills | p) << 1,   # 必须左移
              (dales | p) >> 1)   # 必须右移
    # 错误写法：(hills | p) 或 (hills | p) >> 1

12.6 重复访问标记

# 单词搜索错误：标记后未恢复
def backtrack(i, j, k):
    if board[i][j] != word[k]: return False
    board[i][j] = '#'  # 标记
    # ... 递归
    # 错误：忘记 board[i][j] = word[k]
    return False

12.7 终止条件错误

# 子集问题：终止条件不是 len(path) == n，而是每次都收集
# 错误：
def backtrack(start, path):
    if len(path) == n:  # 错误，会漏掉非满子集
        result.append(path[:])
        return
    # ...

# 正确：
def backtrack(start, path):
    result.append(path[:])  # 每个节点都是子集
    for i in range(start, len(nums)):
        # ...

12.8 排序顺序与剪枝假设冲突

# 错误：组合总和用升序，但需要降序剪枝
# 必须根据剪枝条件选择排序顺序
# candidates.sort() → 升序，candidates[i] > remaining 时 break（后续更大）
# candidates.sort(reverse=True) → 降序，candidates[i] < remaining 时... 但要小心

12.9 多解收集与剪枝交互

# 错误：找所有解时过早 return
def backtrack(...):
    if found_one_solution:
        return True  # 错误：会漏掉其他解
    # ...

# 正确：
def backtrack(...):
    if found_one_solution:
        result.append(...)
        return  # 不返回 True，继续搜索