Hello 算法回溯算法章节练习精解：状态回退、剪枝策略与全排列实现-平芜编程栈

Hello 算法回溯算法章节练习精解：状态回退、剪枝策略与全排列实现

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文以《Hello 算法》（hello-algo）仓库中回溯算法章节的章末练习（日文版原文档，其内容与中文版练习同步）为骨架，逐题拆解其背后的原理，并对照仓库中的真实源码给出可运行、可验证的解答。读完本文，你将能够：解释为什么回溯的“回退”必须把路径与状态标记一起还原；理解全排列/子集和/n 皇后三类经典问题中的剪枝是如何用一行代码起作用的；并完整写出基于布尔数组selected的全排列回溯实现。文中的每一处结论都能在 codes/python/chapter_backtracking 目录找到对应的可执行源码。

练习背后的共同基础：尝试、回退与剪枝

本章节练习涉及的三个“确认问题”和一个“编程练习”，其考察对象本质上都是回溯算法的三要素——尝试（attempt）、回退（backtracking）、剪枝（pruning）。对三要素的系统定义可参见回溯算法正文：算法从初始状态出发深度优先地穷举解空间，每次做选择并更新状态；遇到走不通或已获得解的状态时，撤销刚才的选择、回到上一个状态再试其他分支；而在分支展开前用约束条件提前终止不可能产生解的路径，就是剪枝。

确认问题中反复出现的关键点是：一次“尝试”往往同时修改了多处状态（路径、标记数组、目标剩余值等），因此“回退”也必须把这些修改逐处撤销，两者必须完全对称。下面三道题正是从错误写法、排序约束和几何约束三个角度来检验读者是否真正理解这一点。

确认问题一：排列生成算法会漏掉结果吗

原题：一个回溯算法按1、2、3的顺序尝试生成全部排列。每次选择数字x时执行：①把x加到当前路径末尾；②把x标记为“已使用”；③递归填写下一个位置。递归返回后，某位同学只从路径末尾删除了x，就继续尝试下一个数字。

只回退路径会发生什么

答（子问题 1）：算法首先得到的是[1, 2, 3]，但永远无法得到全部 6 个排列。

原因可以用代码的执行轨迹说明。第一层选1、第二层选2、第三层选3，得到第一个排列[1, 2, 3]；随后第三层弹出3，但由于没有把3恢复为“未使用”，第二层继续遍历时，候选1、2、3里没有任何一个“未使用”的数字可选，函数只能直接返回；再往上一层，第一层同样面临“所有数字仍显示已使用”的局面。整个搜索被锁定在唯一的[1, 2, 3]上，像[1, 3, 2]这类分支从未被真正尝试过。

关键：状态是“路径 + 标记”的联合体

答（子问题 2）：不够。删除路径末尾的x之后，还必须把x重新标记为“未使用”。

原因在于：当前路径和已使用标记共同描述搜索状态。做选择时修改了两处（state追加元素、selected置真），那么回退时就必须把两处都恢复，否则“已使用”标记会把数字永久封禁，导致后续分支失去候选。这正是回溯算法中“撤销（undo）必须与尝试（make）对称”这一铁律的体现。

仓库中正确实现了这一对称性的参考是 permutations_i.py，其核心backtrack循环如下：

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()就是与之一一对应的“回退”。两道撤销语句的顺序虽然不敏感，但缺一不可——这与本确认问题考察的错误写法正好形成对照。运行时若删掉selected[i] = False这一行，输出就会退化成一个排列。

在全排列问题正文中，作者用一棵递归树完整刻画了这种搜索结构：根节点代表初始空状态，从根到叶的每一条路径对应一个排列，叶节点总数是 $n!$。理解“每个状态节点上还有一层selected作为隐形状态”，是判断这段代码是否正确的基础。

确认问题二：数字的选择顺序重要吗

原题：给定排好序的数组[2, 3, 5]和目标值 5，每个数可以被重复选择；算法规定每条搜索路径中的数字只能按从小到大的顺序出现。

升序限制如何消灭重复组合

答（子问题 1）：能得到的不同组合是[2, 3]与[5]。

答（子问题 2）：因为本题把[2, 3]与[3, 2]视为同一种组合，数字的选取顺序不计入答案。若没有“路径内数字必须从小到大”的限制，深度优先搜索会同时生成[2, 3]和[3, 2]两个重复答案（可参考 subset_sum_i_naive.py 的朴素实现，它会输出重复的[4, 5]与[5, 4]）。而规定路径元素按升序出现，就等价于约定选择序列的下标满足 $i_1 \le i_2 \le \dots \le i_m$，从搜索的源头排除了“同数异序”的重复分支，而不是在得到结果后再用哈希去重。

为什么“下一个候选数已经大于剩余值”就可以停止

答（子问题 3）：当前路径为[3]、还差 2 时，下一层的候选从当前元素开始（允许重复选取 3），而候选 3 已经大于剩余值 2。由于数组已排序，3 之后的候选只会更大，也都不可能再加入当前组合，所以可以直接结束这一层的检查。这是“排序 + 一旦超限立即终止”这一剪枝模式的典型应用：排序让“超限”具有单调性，超限点之后的元素必然全部超限，于是可以把线性遍历提前截断。

仓库中 subset_sum_i.py 把上述两个思想落到了代码里：

def backtrack(state, target, choices, start, res): # 子集和等于 target 时，记录解 if target == 0: res.append(list(state)) return # 从 start 开始遍历，避免生成重复子集 for i in range(start, len(choices)): # 剪枝一：子集和超过 target 则结束循环（数组已排序，后边元素更大） if target - choices[i] < 0: break state.append(choices[i]) # start 取 i（而非 i+1），表示每个元素可被重复选取 backtrack(state, target - choices[i], choices, i, res) state.pop()

代码中有两处与本题直接对应：一是for i in range(start, ...)且递归时start传i，既保证了选择序列下标不减（升序、无重复组合），又允许元素重复选取；二是if target - choices[i] < 0: break，即本题第 3 问的“剩余值不足、直接结束本层”。用题目数据验证：把nums = [3, 4, 5], target = 9输入该文件并运行，输出的正是[3, 3, 3]与[4, 5]，不含重复的[5, 4]。

若题目进一步限定“数组含重复元素且每个元素只能选一次”，则还需在每轮跳过与左侧相同的元素，即“相等元素剪枝”，完整解法见 subset_sum_ii.py 与子集和问题正文。

确认问题三：下一枚皇后可以放在哪些位置

原题：在一个4 × 4棋盘上按行放置皇后，行、列下标都从 0 开始；目前已在(0, 1)和(1, 3)放置皇后，现在要在第 2 行放置下一个皇后。

逐列排查同列与同对角线冲突

答（子问题 1）：第 1 列和第 3 列已经有皇后，因此位置(2, 1)与(2, 3)因“同列”被排除。

答（子问题 2）：剩余候选只有(2, 0)与(2, 2)。逐一检查两条对角线：主对角线上所有格子的row - col恒等，次对角线上所有格子的row + col恒等。

(2, 2)：row + col = 4，与(1, 3)的row + col = 4相同，说明两者位于同一条次对角线上，因此排除；
(2, 0)：row - col = 2、row + col = 2，与两个已有皇后的row - col（分别为 −1、−2）和row + col（分别为 1、4）均不相同，且列 0 也没有皇后。

答（子问题 3）：第 2 行可以尝试的位置只有(2, 0)。

特别要注意解答中强调的一点：“当前能放”只代表这一格不与已有皇后冲突，并不代表棋盘一定能被填完。回溯的意义在于：若继续放置到某一行发现无路可走，就回到更早的行、撤掉之前的某个皇后改放其他列，再重新向下搜索。

源码中的 O(1) 剪枝是如何设计的

仓库 n_queens.py 为这道题提供了完整的工业化写法。它用三个布尔数组记录冲突信息，使“该格是否可放”的判断降为 O(1)：

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的取值范围是 $[-n+1, n-1]$，代码用加n - 1的方式把主对角线编号映射到非负下标，因此主、次对角线数组的长度都是2 * n - 1。这与确认问题中的手工排查逻辑完全一致：逐行放置天然避免“同行”，cols处理“同列”，diags1（row - col）与diags2（row + col）分别处理两种对角线。运行时把n = 4输入该文件，会输出 4 皇后问题的全部 2 种摆法，其中一种即从(0, 1)、(1, 3)、(2, 0)继续推进得到，完整示意可对照n 皇后问题正文中的棋盘图理解。

编程练习精解：无重复元素的全排列

题面：整数数组nums至少包含一个元素，且各元素互不相同。请列出把每个元素各使用一次所能形成的全部排列，将每一种排列作为一个数组返回；结果中各排列的先后次序不作要求。要求使用回溯，并用布尔数组记录每个位置的元素是否已选入当前排列。

题意与三条提示的含义

原文档给出的三条提示，恰好对应回溯框架的三个动作：

递归深度表示正在填写排列中的第几个位置——递归进入第几层，就对应state中已有几个元素；
每一层只尝试尚未使用的元素——这正是“重复选择剪枝”，靠布尔数组完成；
路径长度达到nums的长度时，把它的副本加入答案——注意必须是state的副本（如list(state)），否则后续回退修改state时，已经记入答案的列表也会被一并改动。

完整参考实现

permutations_i.py 就是本练习的标准答案式实现：

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() def permutations_i(nums: list[int]) -> list[list[int]]: res = [] backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res) return res

对照“确认问题一”可知，第 26～27 行的selected[i] = False与state.pop()正是那个极易被遗漏的“对称回退”；若注释掉标记复位，本程序同样只能输出一个排列。剪枝还带来了可量化的收益：没有selected时搜索空间规模为 $O(n^n)$，引入“不重复选择”剪枝后缩小到 $O(n!)$（推导见全排列问题正文）。

运行与验证

在仓库根目录直接运行（仓库只读，仅做运行验证即可）：

python codes/python/chapter_backtracking/permutations_i.py

对nums = [1, 2, 3]，控制台会输出全部 6 个排列。你还可以把main中的输入换成其他互异数组（例如[1, 2]应得到 2 个排列、[1]应得到 1 个排列）来验证边界情况。

与另一类解法的区别

本题与 LeetCode 第 46 题 “Permutations” 对应。leetcode 上常见的题解采用交换法：在递归中通过交换数组元素，把已选元素依次挪到数组前部。而本练习规定采用布尔数组selected方案：用一个与choices等长的布尔数组记录“哪些下标已被选走”，两者都能避免同一元素被重复选取，但状态表示与代码结构不同——前者原地交换、不额外维护“已选列表”，后者显式维护state与selected，更贴近本书“状态 + 选择 + 剪枝”的统一回溯框架，也更容易与确认问题一的讨论衔接。

如果数组包含重复元素且要求返回不重复的排列，只需在每轮开启一个哈希集合duplicated做“相等元素剪枝”，完整实现见 permutations_ii.py。它与selected的作用范围不同：selected全程唯一、防止元素在同一排列中重复出现；duplicated每轮独立、保证相等的元素在某一轮只被尝试一次。

小结：练习考点与仓库知识映射

把本章练习的四个问题与对应知识点、源码和延伸阅读梳理如下，便于复习与检索：

练习问题	核心考点	印证源码	延伸阅读
排列只回退路径会漏解	尝试/回退必须对称，路径与`selected`需一起还原	permutations_i.py	全排列问题
数字选择顺序是否重要	排序 + 升序（下标不减）去重；“超限即 break”剪枝	subset_sum_i.py	子集和问题
下一枚皇后的位置	同列剪枝、主/次对角线用`row±col`判冲突	n_queens.py	n 皇后问题
无重复元素全排列	布尔数组`selected`+ 解副本 + 对称回退	permutations_i.py	回溯算法正文