Hello 算法回溯章节练习详解：从状态回退、有序去重到 N 皇后剪枝的完整解题指南

本篇技术文章基于《Hello 算法》回溯算法章节的练习文档展开，完整覆盖原文档的三道知识巩固题（排列回退缺陷、组合搜索的有序性约束、N 皇后合法位置判定）与一道编程练习（无重复元素的全排列），并结合仓库中 Python 参考实现逐题拆解。读完本篇，你将能够：准确识别"只做一半回退"导致回溯失效的典型 Bug；理解 start 下标约束与排序后 break 剪枝如何避免重复子集；掌握 N 皇后中列与两条对角线的冲突判定方法，并写出带布尔数组的完整全排列回溯代码。

一、排列算法中"只删路径、不还原标记"的缺陷

原文档第一道知识巩固题描述了一个带有缺陷的回溯算法：按 1、2、3 的顺序尝试生成全部排列，每次选择数字 x 时执行三步操作——把 x 加到当前路径末尾、把 x 标记为"已使用"、递归填写下一个位置。但递归返回后，只从路径末尾删除了 x，没有把 x 重新标记为"未使用"。题目问两个问题：

1. 算法首先得到哪个排列？它还能得到全部 6 个排列吗？
2. 递归返回上一层前，只删除路径末尾的数字是否足够？如果不够，还需要做什么？

原文档参考答案：算法首先得到 [1, 2, 3]，但无法得到全部排列——虽然返回时路径变短了，数字 1、2、3 的"已使用"标记仍未恢复，后续分支没有可选数字。只删路径末尾不够，还必须把 x 重新标记为"未使用"：当前路径和已使用标记共同描述搜索状态，选择时修改了两处，回退时必须把两处都恢复，其他分支才能再次选择 x。

这道题直指回溯算法的核心纪律：回退必须与尝试严格互逆。仓库中正确的参考实现位于 permutations_i.py，其 backtrack 函数完整地演示了这一点：

def backtrack(state, choices, selected, res):
    """回溯算法：全排列 I"""
    # 当状态长度等于元素数量时，记录解
    if len(state) == len(choices):
        res.append(list(state))
        return
    # 遍历所有选择
    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()

注意"尝试"阶段修改了两个状态变量（selected[i] = True 与 state.append(choice)），"回退"阶段则对称地撤销了这两个变量（selected[i] = False 与 state.pop()）。这正是原题答案中"选择时修改了两处，回退时也必须把两处都恢复"的代码级体现。此外还有一个细节：记录解时使用 res.append(list(state)) 存入的是 state 的副本，因为 state 在后续回退中会被不断修改，若直接引用则所有结果都会退化为同一个空列表。

下图展示了全排列 I 的搜索树，红色"剪枝"标记的正是因元素已被选而剪掉的分支——如果标记不回退，这些本应在兄弟分支中重新出现的数字将永久失效：

作为对照，仓库中的 permutations_ii.py 处理含重复元素的数组 [1, 2, 2]，在同样的 selected 标记之外又增加了一个 duplicated 集合做同层去重，但回退逻辑与上述代码结构完全一致——这也从侧面说明"尝试/回退成对出现"是本章所有回溯实现的通用骨架。

二、数字的选择顺序：有序性约束与排序后剪枝

第二道题设定如下：给定排好序的数组 [2, 3, 5] 和目标值 5，每个数可以重复选择，且每条搜索路径中的数字只能按从小到大的顺序出现。三个小问题：

1. 能得到哪些不同的组合？
2. 为什么同一组数字不需要按不同顺序重复搜索？"从小到大"的限制起到了什么作用？
3. 当前路径为 [3]、还差 2 时，下一个候选数是 3，为什么此时可以停止检查这一层后面的所有候选数？

原文档参考答案：

1. 不同的组合为 [2, 3] 和 [5]。
2. 本题把 [2, 3] 和 [3, 2] 看作同一种组合，选择顺序不计入答案；规定路径中的数字从小到大出现，就能在搜索时直接跳过 [3, 2] 这类重复组合。
3. 当前还差 2，而候选数 3 已经大于 2；因为数组已排好序，3 后面的候选数只会更大，也不可能加入当前组合，所以可以直接结束这一层的检查。

这道题考察的是"子集和"类问题中两种经典去重/剪枝手段的组合，其完整实现在 subset_sum_i.py 中：

def backtrack(state, target, choices, start, res):
    """回溯算法：子集和 I"""
    # 子集和等于 target 时，记录解
    if target == 0:
        res.append(list(state))
        return
    # 遍历所有选择
    # 剪枝二：从 start 开始遍历，避免生成重复子集
    for i in range(start, len(choices)):
        # 剪枝一：若子集和超过 target ，则直接结束循环
        # 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if target - choices[i] < 0:
            break
        # 尝试：做出选择，更新 target, start
        state.append(choices[i])
        # 进行下一轮选择
        backtrack(state, target - choices[i], choices, i, res)
        # 回退：撤销选择，恢复到之前的状态
        state.pop()

把源码与题目三问逐一对应：

• 小问 2 对应"剪枝二"：for i in range(start, len(choices)) 让下一层的选择只能从当前下标 i 开始（递归传入 i 而非 i + 1，从而允许重复选择当前元素），这在结构上就禁止了 [3, 2] 这类"倒序"路径，与题目中"从小到大"的规定完全等价；
• 小问 3 对应"剪枝一"：if target - choices[i] < 0: break 正是"还差 2 而候选是 3 时直接结束这一层"的代码化表达，它依赖的前置条件是入口处 nums.sort() 保证的有序性——源码注释明确指出"数组已排序，后边元素更大，子集和一定超过 target"。

下图是子集和 I 的搜索树，图中"剪枝：跳过 3, 4"等灰色分支正是 start 下标约束与 break 共同剪掉的重复子集与超额分支：

需要强调的是这两处剪枝的角色分工：start 下标约束解决"同一组合的多种排列"（去重），排序后的 break 解决"不可能达标的超额分支"（剪枝），二者叠加才使搜索树显著变小。

三、N 皇后：下一枚皇后可以放在哪些位置

第三道题描述了一个 4×4 棋盘（行、列下标均从 0 开始），已在 (0, 1) 和 (1, 3) 放置皇后，现在要在第 2 行放置下一个皇后。题目分三问：

1. 哪些列会因为"同列"而被排除？
2. 在剩余列中，哪些位置会因为"同一条对角线"而被排除？
3. 第 2 行还剩哪些位置可以尝试？

原文档参考答案：

1. 第 1 列和第 3 列已有皇后，位置 (2, 1) 和 (2, 3) 被排除；
2. 剩余位置中，(2, 2) 与 (1, 3) 位于同一条对角线上，也被排除；(2, 0) 与已有两个皇后都不在同列或同一条对角线上；
3. 第 2 行可以尝试的位置只有 (2, 0)。这一步只说明当前放置合法，之后若无法完成棋盘，仍需回退并尝试更早的其他选择。

手动判定对角线冲突依赖"两个格子是否在同一条对角线"的直觉；而代码实现需要把这一直觉转换为可 O(1) 查询的索引运算。仓库实现 n_queens.py 给出了标准答案：

def backtrack(row, n, state, res, cols, diags1, diags2):
    """回溯算法：n 皇后"""
    # 当放置完所有行时，记录解
    if row == n:
        res.append([list(row) for row in state])
        return
    # 遍历所有列
    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

三个冲突维度分别映射为三个布尔数组，其索引推导与题目中的对角线判定一一对应：

冲突维度	数组	索引规则	说明
同列	cols（长 n）	col	与题目小问 1 的"第 1 列、第 3 列已有皇后"对应
主对角线（↘）	diags1（长 2n-1）	row - col + n - 1	同一 ↘ 对角线上所有格子差值 row - col 相同，加 n-1 偏移避免负索引
次对角线（↗）	diags2（长 2n-1）	row + col	同一 ↗ 对角线上所有格子之和 row + col 相同

用题目数据验证：(2, 2) 的次对角线索引为 2 + 2 = 4，与已放置的 (1, 3)（1 + 3 = 4）相同，恰好被 diags2 判为冲突——这就是题目小问 2 中"(2, 2) 与 (1, 3) 同对角线"的算术化表述；而 (2, 0) 的主对角线索引 2 - 0 + 3 = 5、次对角线索引 2 + 0 = 2、所在列 0，均未被占用，因此是第 2 行唯一可尝试的位置。

从源码结构看，state[row][col] = "Q" 与三处 True 赋值构成"尝试"，紧随其后的 state[row][col] = "#" 与三处 False 赋值构成"回退"，再次印证了第一题总结的"改几处、恢复几处"原则；同时题目答案第 3 问的最后一句——"之后若无法完成棋盘，仍需回退并尝试更早的其他选择"——对应的正是递归调用返回后执行回退语句、外层 for col 循环继续遍历下一个 col 的过程。下图展示了 4 皇后问题逐行放置的完整搜索树，被灰色填充的节点即为被列/对角线约束剪掉的分支：

四、编程练习：无重复元素的全排列

文档"编程练习"部分给出了一道经典题目：整数数组 nums 至少包含一个元素且元素互不相同，请列出把这些元素各使用一次所能形成的全部顺序，每种顺序作为一个数组返回，排列先后次序不作要求；要求使用回溯，并用布尔数组记录每个位置的元素是否已经选入当前排列。原文档给出的三条解题提示为：

1. 递归深度表示正在填写排列中的第几个位置；
2. 每一层只尝试尚未使用的元素；
3. 路径长度达到 nums 的长度时，把它的副本加入答案。

permutations_i.py 即这道题的完整参考解答，permutations_i(nums) 入口函数构造初始状态并启动搜索：

def permutations_i(nums: list[int]) -> list[list[int]]:
    """全排列 I"""
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res

以 nums = [1, 2, 3] 为例，其运行输出为：

输入数组 nums = [1, 2, 3]
所有排列 res = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

逐条对照三条解题提示的实现位置：提示 1 体现在"递归深度 = 已填位置数"，即终止条件 len(state) == len(choices)（路径长度达到 n 即填满全部位置）；提示 2 体现在 if not selected[i] 这一剪枝判断，布尔数组 selected 的初始值 [False] * len(nums) 由入口函数一次性构造；提示 3 体现在 res.append(list(state))——list(state) 的"副本"二字是关键，缺失它会与"回退"阶段发生别名冲突。

仓库文档还附带了一个方法学说明：另一种常见解法通过交换数组元素把已选元素依次放到数组前部（即 swap + 回溯 写法），本题解法则使用布尔数组记录每个元素是否已选。两种方法都能避免同一元素被重复选择，但代码结构不同——前者不需要额外标记数组，但每次尝试/回退都要对数组做两次对称交换；后者状态更直观，代价是一个 O(n) 的布尔数组。理解这两种等价结构，配合前面三道知识巩固题的"回退完整性、有序去重、约束判定"三个考点，就构成了本章练习要求的完整能力面。

五、参考实现与延伸阅读

本文章所引用的全部参考实现均位于仓库 codes/ 目录，同一套回溯代码在 Python、Java、C++、C、Go、Rust 等十余种语言中均有对应实现，可按语言目录自行切换查看：

• permutations_i.py：全排列 I，布尔数组标记 + 成对回退；
• permutations_ii.py：全排列 II，在布尔数组基础上叠加同层去重集合；
• subset_sum_i.py：子集和 I，start 下标去重 + 排序后 break 剪枝；
• n_queens.py：N 皇后，列与两条对角线的 O(1) 冲突判定；
• 本章正文 回溯算法：回溯"尝试、回退、剪枝"框架代码的推导过程，以及 N 皇后问题、全排列问题、子集和问题 三个完整案例的解析。

小结：本章练习的四个考点可以收敛为三条工程准则——第一，回退必须与尝试严格互逆，凡是"尝试"阶段改动了的状态（路径、标记数组、棋盘与对角线索引），"回退"阶段要逐一恢复，遗漏任何一处都会让搜索树静默地丢失解；第二，对于"组合"类答案，用 start 下标或"从小到大"的有序性约束从结构上消灭重复排列，再配合排序后 break 剪掉超额分支；第三，对 N 皇后这类约束问题，把"同列/同对角线"的几何直觉翻译成 col、row - col、row + col 三个可 O(1) 索引的数组，是剪枝能否高效执行的关键。