Backtracking Algorithm Summary in Hello Algo: Exhaustive Search, Pruning, and the Three Canonical Problems

本文是对《Hello Algo》英文版回溯算法章节 summary.md 的知识收束与仓库级延伸解读：从"穷举 + 深度优先遍历解空间"的本质出发，梳理"尝试/回退/剪枝"三大操作，并逐一拆解全排列、子集和、n 皇后三个经典回溯问题各自的去重技巧与代码实现。读者读完既能复述章节的关键结论，也能对照本仓库 python 与 c 等语言的完整源码，理解 selected、duplicated、start、cols/diags1/diags2 这些剪枝手段背后真实的调用关系。

章节全景：本章讲清了什么

回溯章节由四篇正文与一份小结构成：

文档	核心问题
backtracking_algorithm.md	回溯的本质、尝试与回退、剪枝、通用框架与术语
permutations_problem.md	含/不含重复元素的全排列与两类剪枝
subset_sum_problem.md	元素可重复/数组含重复值的子集和问题
n_queens_problem.md	n 皇后的行列与对角线约束处理
exercises.md	配套练习题

本小结文档的 "Key Review" 用十条结论浓缩了上述全部内容，"Q & A" 则澄清了回溯与递归的关系。下面逐条展开，并在每条旁标注仓库中的可运行证据。

回溯的本质：对解空间的深度优先穷举

小结第一条指出：回溯算法本质上是穷举搜索法，它通过对解空间做深度优先遍历（depth-first search）来寻找满足条件的解，找到即记录，直到找全所有解或遍历完毕。

这一表述在仓库中可直接印证：章节正文 backtracking_algorithm.md 用一个二叉树前序遍历问题（查找所有值为 7 的节点）引出回溯，因为前序、中序、后序遍历本身就是深度优先搜索。对应实现见 preorder_traversal_i_compact.py，其只负责"找到并记录"，尚未包含回退逻辑。

尝试与回退：方向相反的一对操作

小结第二条强调：回溯的搜索过程由 尝试（attempt）与回退（backtrack） 两部分组成——通过深度优先搜索尝试各种选择，遇到违反约束的情况就撤销上一次选择、回到上一个状态继续尝试别的分支。尝试与回退是方向相反的两种操作。

正文用一个加强版例题来说明"回溯不止发生在函数返回时"：不仅要找值为 7 的节点，还要返回从根到这些节点的完整路径。为此需要引入路径列表 path：

def pre_order(root: TreeNode):
    """前序遍历：例题二"""
    if root is None:
        return
    # 尝试
    path.append(root)
    if root.val == 7:
        # 记录解
        res.append(list(path))
    pre_order(root.left)
    pre_order(root.right)
    # 回退
    path.pop()

这段代码清晰地展示了"尝试 = 把当前节点加入 path"、"回退 = 递归返回后把节点移出 path"，以此恢复尝试前的状态。pre_order 中对左右子树的两次递归调用、叶子节点遍历结束后函数返回，都属于回退时机。全量实现见 preorder_traversal_ii_compact.py，C 版本见 preorder_traversal_ii_compact.c。

剪枝：用约束砍掉注定失败的搜索分支

小结第三条指出：回溯问题通常含有多条约束，约束可用来实现剪枝（pruning），提前终止无意义的搜索分支，显著提升搜索效率。

正文例题三要求在找值为 7 的路径时，路径中不得包含值为 3 的节点，于是"遇到值为 3 的节点立刻返回、不再深入"就是一次剪枝。仓库实现见 preorder_traversal_iii_compact.py 与 preorder_traversal_iii_compact.c。

通用回溯框架与术语对照

为了复用尝试/回退/剪枝这套逻辑，正文 backtracking_algorithm.md 提取了一个通用框架：state 表示当前问题状态，choices 表示当前状态下可做的选择。其 Python 形态如下：

def backtrack(state: State, choices: list[choice], res: list[state]):
    """回溯算法框架"""
    # 检查是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
        # 停止搜索
        return
    # 遍历所有选择
    for choice in choices:
        # 剪枝：检查选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            backtrack(state, choices, res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

框架对应的通用术语（Solution / Constraint / State / Attempt / Backtracking / Pruning）已在正文中以表格列出。仓库中 preorder_traversal_iii_template.c 是把例题三按这套框架逐一拆成 isSolution()、recordSolution()、isValid()、makeChoice()、undoChoice() 的真实范本（backtrack 位于该文件中部），Python 对应模板见 preorder_traversal_iii_template.py。

值得注意的是：例题三要求找到一条路径后继续搜索，因此模板中记录解之后不加 return，这一点正文用图对比了有无 return 的差异。许多回溯题只需替换 state、choices 并实现框架里的各方法即可套用，这也是"框架化"的价值所在。

适用范围：搜索、约束满足与组合优化

小结第四条给出定位：回溯主要用于求解搜索问题与约束满足问题；组合优化问题虽然也能用回溯求解，但通常存在更高效的方案。正文据此把典型应用分为三类：

• 搜索问题：全排列、子集和、汉诺塔；
• 约束满足问题：n 皇后、数独、图着色；
• 组合优化问题：0-1 背包、旅行商（TSP）、最大团。

文档特别提醒：0-1 背包通常用动态规划获得更高时间效率；TSP 是著名 NP-Hard 问题，常用遗传算法、蚁群算法等；最大团可借助贪心等启发式算法。这正是本章反复强调"剪枝 + 启发式"两条优化路径（见 backtracking_algorithm.md 的 Advantages and Limitations 一节：回溯时间可达指数级或阶乘级，递归深度大时空间开销也不容忽视）。

经典问题一：全排列与两类剪枝

小结第五、六条针对全排列：

• 不含重复元素：用布尔数组 selected 记录每个元素是否已被选取，从而剪掉"重复选择同一元素"的分支，保证每个元素恰好被选一次；
• 含重复元素：最终会产出重复排列，需增加约束使相等元素在同一轮中只能被选一次，通常借助哈希集合（如 duplicated）实现。

从源码看，这两类剪枝的"管辖范围"完全不同。以 Python 实现为例：

# 遍历所有选择
duplicated = set[int]()
for i, choice in enumerate(choices):
    # 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
    if not selected[i] and choice not in duplicated:
        # 尝试：做出选择，更新状态
        duplicated.add(choice)  # 记录选择过的元素值
        selected[i] = True
        state.append(choice)
        # 进行下一轮选择
        backtrack(state, choices, selected, res)
        # 回退：撤销选择，恢复到之前的状态
        selected[i] = False
        state.pop()

区别可概括为：

• selected（剪"重复选择"）：整个搜索过程只有一份，记录当前状态 state 已包含哪些元素，作用是防止同一元素在 state 里反复出现（覆盖的是"同一元素"这一维度，作用在整条路径上）；
• duplicated（剪"相等元素"）：每一轮选择（每次 backtrack 调用）各持有一份，记录本层 for 循环已试过哪些元素值，作用是保证相等的元素在一轮里只被尝试一次（作用在单个搜索层的兄弟分支之间）。

小结给出 duplicated 通常用哈希集合实现，正文中 Python 正是 duplicated = set[int]()；C 语言因无原生哈希集合，使用定长布尔数组按元素值索引（见 permutations_ii.c 第 24 行 bool duplicated[MAX_SIZE]）。边界情况在代码中同样成立：如果输入元素都互不相同，n 个元素共有 n! 个排列，记录解需 O(n) 复制，故时间复杂度 O(n!·n)；递归栈 O(n)、selected O(n)、同时存在的 duplicated 集合至多 n 个各占 O(n)，故空间复杂度 O(n²)。剪枝前后解空间规模由 O(nⁿ) 收敛到 O(n!)。

无重复版本可对照 permutations_i.py 与 permutations_i.c。

经典问题二：子集和的"排序 + start"剪枝体系

小结第七、八条针对子集和：

• 由于集合无序而搜索过程按顺序输出，会生成重复子集。对策是回溯前先排序，并用一个变量（start）指示每轮遍历的起点，从而剪掉产生重复子集的分支；
• 当数组中存在相等元素时，利用"数组已排序"这一前提，通过判断相邻元素是否相等来实现剪枝，保证相等元素每轮只选一次。

子集和问题还涉及一个与全排列不同的设定——元素可被重复选取（变体一），因此不需要 selected 数组。先看"无重复元素但可重复选取"的朴素解 subset_sum_i_naive.py：它对 [3, 4, 5]、target=9 会输出 [3,3,3],[4,5],[5,4]，其中 [4,5] 与 [5,4] 互为重复子集。用"事后对结果列表去重"并不优雅：元素多、target 大时会产生海量重复分支，且子集比较需先排序再逐元素比对，代价高昂。正确做法是搜索过程中剪枝。

变体一：元素可重复选取

正式解 subset_sum_i.py 的改进点：

1. 引入 start：做出选择 nums[i] 后，下一轮从下标 i 开始遍历，保证选取序列下标满足 i₁ ≤ i₂ ≤ … ≤ iₘ，从而保证子集唯一；
2. 回溯前对数组排序；遍历到子集和超过 target 时直接结束循环（后续元素更大，和必然超 target）；
3. 省略求和变量 total，改用 target 递减，当 target == 0 时记录解。

变体二：数组含重复值、每个元素至多选一次

subset_sum_ii.py 在该基础上叠加"相等元素每轮只选一次"：

for i in range(start, len(choices)):
    # 剪枝一：若子集和超过 target ，则直接结束循环
    if target - choices[i] < 0:
        break
    # 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
    if i > start and choices[i] == choices[i - 1]:
        continue
    # 尝试：做出选择，更新 target, start
    state.append(choices[i])
    # 进行下一轮选择
    backtrack(state, target - choices[i], choices, i + 1, res)
    # 回退：撤销选择，恢复到之前的状态
    state.pop()

这里同时存在四类剪枝，C 版本 subset_sum_ii.c 的注释对它们做了明确编号：剪枝一（子集和超 target 即跳过/结束）、剪枝二（从 start 开始避免重复子集）、剪枝三（从 start 开始避免重复选取同一元素——此处下一轮起点为 i + 1，天然保证每个元素至多选一次）、剪枝四（i > start 且与左邻相等则跳过）。选取 start 的妙处在于：它同时服务"去重子集"与"元素至多一次"两个目标。

经典问题三：n 皇后的行、列、对角线约束

小结第九、十条聚焦 n 皇后：

• 在 n×n 棋盘放 n 个皇后使其互不攻击，约束包括行、列、主/次对角线；
• 为满足行约束，采用逐行放置策略，保证每行恰好一个皇后；
• 列约束用数组 cols 记录每列是否已有皇后；对角线约束用两个数组 diags1、diags2 分别记录主、次对角线上是否已有皇后。难点在于找出刻画同一主（次）对角线上格子的行列下标规律。

仓库实现 n_queens.py 中可看到完整的行列逻辑：

# 遍历所有列
for col in range(n):
    # 计算该格子对应的主对角线和次对角线
    diag1 = row - col + n - 1
    diag2 = row + col
    # 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
    if not cols[col] and not diags1[diag1] and not diags2[diag2]:
        # 尝试：将皇后放置在该格子
        state[row][col] = "Q"
        cols[col] = diags1[diag1] = diags2[diag2] = True
        # 放置下一行
        backtrack(row + 1, n, state, res, cols, diags1, diags2)
        # 回退：将该格子恢复为空位
        state[row][col] = "#"
        cols[col] = diags1[diag1] = diags2[diag2] = False

关键下标规律是：同一主对角线上所有格子满足 row - col 为常数，同一副对角线上所有格子满足 row + col 为常数。由于 n×n 矩阵中 row - col ∈ [-n+1, n-1]、row + col ∈ [0, 2n-2]，两类对角线的数量都是 2n-1，因此 diags1、diags2 长度均为 2n-1；C 代码 n_queens.c 用 diag1 = row - col + n - 1 把可能为负的下标平移到非负区间，Python 实现亦采用同样的平移写法。逐行放置本身就相当于剪掉"同一行出现多个皇后"的所有分支，这也是"行约束天然满足"的原因。

复杂度上：逐行放 n 个皇后，仅考虑列约束时各行的可选数为 n、n-1、…、2、1，用时 O(n!)；记录解时复制 n×n 棋盘需 O(n²)，因此整体时间复杂度 O(n!·n²)，而对角线剪枝在实际运行中还能进一步大幅压缩搜索空间。state 占 O(n²)，cols、diags1、diags2 各占 O(n)，最大递归深度 n，故空间复杂度 O(n²)。

回溯的代价与两条效率优化路径

结合正文 backtracking_algorithm.md 的 Advantages and Limitations 一节，可对小结结论作进一步收束：

• 优点：能找到全部可行解；配合合理剪枝时效率可观；
• 代价：大规模问题下时间可达指数级/阶乘级；递归需保存当前状态（路径、剪枝辅助变量），深度大时空间开销巨大；
• 优化路径：一是剪枝——跳过注定无解的分支；二是启发式搜索——在搜索中引入策略或估值，优先探索最可能产生合法解的分支。

对很多搜索与约束满足问题，回溯仍是最合适的方案，因为无法预知哪些选择会导向合法解，必须遍历所有可能；关键是做好剪枝。

答疑：回溯与递归究竟是什么关系

小结最后的 Q & A 给出了一个值得反复琢磨的结论：

回溯是一种算法策略，递归则更应被看作一种工具。

• 回溯通常借助递归实现，但回溯只是递归的一种应用——即递归在搜索问题中的运用；
• 递归的结构体现"把问题分解为子问题"的解题范式，常被用于分治、回溯以及动态规划（记忆化递归）。

仓库可以给出跨章节的佐证：

• 回溯借递归实现：本小节所有示例（permutations_ii.py、subset_sum_ii.py、n_queens.py）的 backtrack 均在函数体内调用自身；
• 递归用于分治：二分查找递归版 binary_search_recur.c、建树问题 build_tree.c 等体现"分解为子问题"的范式；
• 递归用于动态规划（记忆化）：带备忘的爬楼梯 DFS 版见 climbing_stairs_dfs_mem.c（同目录下还有 climbing_stairs_backtrack.c、climbing_stairs_dp.c 可对照回溯、记忆化递归与迭代 DP 三种写法）。

一句话概括：想学回溯，先要熟练递归；但会用递归，不等于理解了回溯——回溯特有的贡献在于用状态恢复（撤销选择）在解空间里"进退自如"，并用剪枝控制搜索范围。

动手验证与延伸阅读

本仓库为每个例题都提供了带 main / if __name__ == "__main__" 驱动的完整可运行源码（Python 直接运行文件即可打印树结构、棋盘与结果，如 python codes/python/chapter_backtracking/permutations_ii.py；C 版本已纳入 chapter_backtracking 的 CMakeLists.txt 构建目标）。除 Python 与 C 外，全排列、子集和、n 皇后在 codes 下的 Java、C++、Go、Swift、Rust、TypeScript、Dart、Kotlin 等语言目录均有同名实现，可与本文对照学习。

若想检验掌握程度，可继续完成 exercises.md 的练习；若要回顾回溯的三步入门（穷举本质 → 尝试/回退 → 剪枝），可回到 backtracking_algorithm.md 精读其配图与术语表。