Hello 算法：回溯算法章节知识总结——从全排列、子集和到 n 皇后问题的剪枝实战

2026-09-07 16:44:29作者：羿妍玫Ivan

本文基于仓库内日文版《Hello 算法》回溯章节总结文档展开，完整承接其中的"要点回顾 + Q&A"骨架，并结合仓库中 chapter_backtracking 目录下的多语言实现（本文以 Python 为例）逐条印证核心机制。读者读完可系统掌握回溯算法的本质与适用边界，理解"尝试—回退—剪枝"三要素，并能在全排列、子集和、n 皇后三类经典问题上独立分析去重与剪枝策略。

回溯的本质：在解空间上的深度优先全搜索

章节总结的第一条要点指出：回溯算法的本质是"全搜索法"（全探索），通过深度优先的方式遍历解空间，搜索满足条件的解。搜索过程中，一旦遇到满足条件的解就记录，直到找齐所有解或穷尽整个搜索空间为止。

在二叉树章节中已经介绍过的前序、中序、后序遍历都属于深度优先搜索（DFS）。回溯正是把这种 DFS 思想推广到"解空间树"上：把搜索中可能到达的每一个状态视为一个节点，状态的转移视为边，于是求所有可行解就等价于在状态树上做深度优先遍历并记录终止状态。
由于回溯是一种"遍历到底、无路可走再折返"的策略，它天然适合需要枚举"全部解"的场景，例如后面要展开的全排列（所有排列）、子集和（所有组合）、n 皇后（所有放置方案）。

需要强调的是，回溯的遍历对象不是数据本身，而是由 state（当前状态）与 choices（可选择项）逐步构建出来的解空间，这一点在阅读仓库中的通用回溯框架时更容易体会。

尝试与回退：一对互为逆向的操作

总结第二条将回溯的搜索过程概括为**"尝试"与"回退"**两个动作：

沿着深度的方向做出新的选择、进入下一个状态，称为一次"尝试"（試行）；
当发现当前选择无法继续、或已经满足解的条件需要另辟蹊径时，撤销最近一次选择、恢复到此前的状态，再尝试其他分支，称为一次"回退"（戻る）。

两者是方向相反的互逆操作。这一点在代码层面体现得最直观：以仓库中的全排列 I（无重复元素）Python 实现为例：

for i, choice in enumerate(choices):
    if not selected[i]:                 # 剪枝：跳过已选择的元素
        selected[i] = True              # 尝试：做出选择
        state.append(choice)
        backtrack(state, choices, selected, res)  # 进入下一层
        selected[i] = False             # 回退：撤销选择
        state.pop()                     # 恢复 state 与 selected

尝试（append + selected=True）与回退（pop + selected=False）严格对称，回退并不是简单的函数返回，而是把状态恢复原样，这正是回溯与普通递归遍历的关键区别。树上的"找路径"问题可以进一步看到"路径维护"中的尝试与回退，例如 preorder_traversal_ii_compact 中，进入节点时 path.append(root)、离开节点前 path.pop()。

剪枝：用约束条件砍掉无用分支

总结第三条强调：回溯问题通常带有多个约束条件，这些约束可以用来"剪枝"——在深入某个分支之前先判断其是否还有希望，提前终止那些注定无解或产生重复解的搜索分支，从而显著提升搜索效率。

剪枝通常写在"尝试"之前的入口处，作用是过滤候选选择。仓库中的二叉树例题 preorder_traversal_iii_compact.py 是最直观的例子：题目要求路径不得包含值为 3 的节点，因此在递归入口直接判断：

if root is None or root.val == 3:
    return      # 剪枝：值为 3 的节点不再深入

而在后文的全排列、子集和、n 皇后问题中，剪枝将从简单的"值判断"升级为借助 selected 数组、哈希集合、排序后相邻比较、行列对角线标记数组等数据结构的复合剪枝。剪枝的丰富程度，往往决定一个回溯算法在工程上的实用价值。

值得指出：回溯的时间代价在极端情况下会很大。日文版章节文档回溯算法概述指出，回溯算法常常需要遍历状态空间中的大量可能性，最坏情况下时间开销可能达到指数级甚至阶乘级——因此剪枝与建模策略不是优化项，而是必要项。

回溯的适用问题类型与边界

总结第四条给出了回溯的应用定位：

搜索问题：如查找所有符合条件的节点、路径或排列——这是回溯的主场；
约束满足问题：如 n 皇后、数独等需要在约束下寻找完整方案的问题；
组合优化问题：回溯也可求解（本质仍是搜索），但往往存在更高效或更契合的专门解法，例如动态规划、贪心算法。因此在遇到组合优化问题时，不要默认套回溯，而应先在"求全部可行解"与"求最优解"之间做区分。

关于回溯与递归的关系，见文末的 Q&A 部分。

全排列问题：用 selected 数组保证"每元素只用一次"

总结第五条对应无重复元素的全排列问题：目标是枚举给定集合中全部元素的所有可能排列。核心难点在于保证"每个元素在整个排列中恰好出现一次"。

仓库中的 permutations_i.py 给出的解法是：引入布尔数组 selected 记录某个下标是否已经被选入当前排列；递归时跳过 selected[i] == True 的元素，从而剪掉"同一元素被重复选中"的分支：

if len(state) == len(choices):          # 所有元素均已排好 → 记录一个解
    res.append(list(state))
    return
for i, choice in enumerate(choices):
    if not selected[i]:                 # 剪枝：下标 i 未被使用才允许尝试
        selected[i] = True
        state.append(choice)
        backtrack(state, choices, selected, res)
        selected[i] = False
        state.pop()

当元素互不相同时，n 个元素共有 n! 个排列；日文版全排列问题文档对该实现的分析结论是：记录每个解时需要复制长度为 n 的列表（O(n)），故时间开销上界为 O(n!·n)；递归深度 n（O(n) 栈空间）加上 selected（O(n)），总体空间为 O(n)。

含重复元素的全排列：每轮用哈希集合去重

总结第六条指出了重复元素带来的新困难：当输入集合中存在相等元素时，朴素回溯会把它们当作不同个体，导致最终结果中出现重复排列。例如 nums = [1, 2, 2]，若不做处理会输出 2 组等价的 [1,2,2] 类排列。

解决思路是：在每一层（每一轮）搜索中，等值的元素只能被选择一次。仓库中的 permutations_ii.py 采用每轮新建一个哈希集合 duplicated 记录本轮已经"尝试过"的值，配合 selected 做双重剪枝：

duplicated = set()                      # 本轮中已选择过的元素值
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()

注意 duplicated 是每轮局部新建的：它只约束"同一轮（排列的同一个位置）不能放相同值"，而不会禁止不同轮次放置相等元素（它们属于不同位置，是合法且不同的排列）。当排列中同时存在的重复副本最多有 n 个时，该方案需要 O(n²) 量级的附加空间。

子集和问题：排序 + 起始下标变量的组合去重

总结第七条涉及子集和问题：从给定正整数集合中找出所有和为 target 的子集。子集（组合）本身不区分元素顺序，但搜索过程按顺序取元素时会把 [1,2] 与 [2,1] 当成不同分支输出，从而产生"顺序不同但集合相同"的重复子集。

仓库中 subset_sum_i.py 的去重方案正是总结所描述的两步：

回溯前先对数组排序（nums.sort()）；
引入起始下标变量 start，每层递归只从 start 开始向后遍历，使下一轮选择的元素下标恒大于等于当前下标，从而剪掉一切"回头选更小元素"的分支，从根源上避免顺序不同的重复组合。

for i in range(start, len(choices)):
    if target - choices[i] < 0:         # 剪枝一：排序后，后续元素只会更大，直接 break
        break
    state.append(choices[i])
    backtrack(state, target - choices[i], choices, i, res)   # 可重复选取 → 起始下标仍为 i
    state.pop()

这段代码同时展示了两种剪枝："和超 target 即 break" 依赖排序带来的单调性，是"值约束剪枝"；"起始下标从 start 开始" 是"结构去重剪枝"。它对应的是"每个元素可无限次使用"的版本。

子集和 II：相邻相等元素剪枝

总结第八条对应输入数组本身含重复元素的场景（每个元素只能用一次）。此时即使有了 start 去重，等值元素仍会在不同分支中被分别取用而产生重复子集，例如 nums = [4, 4, 5]、target = 9 时朴素结果会出现两组 [4, 5]。

仓库中的 subset_sum_ii.py 充分利用了"数组已排序"的前提，在循环内加一条相邻相等判断：跳过与前一个元素相等的选择，从而保证每一轮中相等的元素只会被选取一次：

if i > start and choices[i] == choices[i - 1]:
    continue                            # 剪枝：同层跳过与左侧相等的重复元素
...
backtrack(state, target - choices[i], choices, i + 1, res)  # 每个元素只能使用一次 → 起始下标 i+1

对比两个版本可以归纳出子集和问题的完整剪枝工具包：

剪枝	作用	所属版本
`target - choices[i] < 0` 时 `break`	借助排序单调性，和超 target 提前终止	I / II
起始下标 `start`	禁止回头选择，消除顺序不同的重复子集	I / II
起始下标 `i` vs `i + 1`	控制元素可被无限次使用还是只能使用一次	I（i）/ II（i+1）
`choices[i] == choices[i-1]` 时 `continue`	同层跳过等值元素，消除元素重复导致的重复子集	II

n 皇后问题：行主序 + 四条约束的数组化

总结第九、十条围绕 n 皇后问题：在 n×n 棋盘上放置 n 个皇后，要求任意两个皇后不能互相攻击（不同行、不同列、不在同一主/副对角线）。

行约束通过"逐行放置"的策略天然满足——每行只放一个皇后，从而将问题简化为"为每一行选择合法的列"。仓库中的 n_queens.py 用三个布尔数组完成其余约束的记录与判定：

cols    = [False] * n            # 记录每一列是否已有皇后
diags1  = [False] * (2 * n - 1)  # 主对角线（row - col 恒定）
diags2  = [False] * (2 * n - 1)  # 副对角线（row + col 恒定）

难点正如总结所述，在于把"同一条对角线上所有格子"抽象成可索引的规律。该实现采用两个线性变换：

主对角线判定下标：diag1 = row - col + n - 1（保证取值落在 [0, 2n-2]）；
副对角线判定下标：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          # 回退恢复

从逐行放置的视角看：第 1 行有 n 个选择，考虑列约束后第 2 行剩 n-1 个……因此无剪枝的规模为 O(n!)；又因记录解时需要复制 n×n 的棋盘（O(n²)），日文版n 皇后问题文档给出的时间上界为 O(n!·n²)。state 占用 O(n²)、cols/diags1/diags2 各占 O(n)，故空间复杂度为 O(n²)。实际由于对角线与列约束的剪枝大幅压缩了搜索空间，运行效率通常会好于上述理论最坏上界。