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 算法》开源仓库 回溯章节小结 展开，系统梳理回溯算法的核心机制：以深度优先遍历穷举解空间、"尝试与回退"这对互逆操作、基于约束条件的剪枝，以及框架代码中 state 与 choices 的抽象。读完本文，你将掌握全排列、子集和、$n$ 皇后三道经典题的剪枝设计（selected标记、start起始点、对角线索引规律），并能直接对照仓库中 Python 等十余种语言的实现（chapter_backtracking 代码目录）复现与验证。

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

回溯算法本质是一种穷举法：从初始状态出发，对解空间做深度优先遍历（DFS），逐一"尝试"所有可能的选择组合；每当遇到满足条件的解就记录下来，直到找到所有解或遍历完成。可以把它理解为"结构化的暴力"——暴力在于尝试所有可能，结构化在于用 DFS 的组织方式保证既不遗漏也不重复地覆盖解空间。

在仓库的 回溯算法主文档 中，作者用一个二叉树前序遍历搜索节点值的例题（对应 preorder_traversal_i_compact.py）引入了这一思想：访问每个节点即一次"尝试"，越过叶节点或return回父节点即一次"回退"。当例题升级为"返回根到目标节点的完整路径"（对应 preorder_traversal_ii_compact.py）时，回退就不仅仅是函数返回，还必须在返回前把当前节点从路径path中弹出，恢复尝试之前的状态——这正是回溯区别于普通 DFS 的关键：回退操作要保证"现场"可复原。

剪枝：用约束条件提前结束无效分支

复杂的回溯问题通常包含多个约束条件，而约束条件正是剪枝的依据：在搜索过程中判断某个选择是否合法，若分支继续下去必然不产生解，就提前终止该分支，避免大量无意义的尝试。主文档中的例题三（路径中不包含值为 3 的节点）就演示了这一点，对应实现见 preorder_traversal_iii_compact.py。

剪枝是回溯算法效率优化的第一抓手，第二抓手是启发式搜索：引入策略或估计值，优先搜索最可能产生有效解的路径。对于某些搜索问题和约束满足问题，由于无法预测哪些选择能生成有效解，必须遍历所有可能——此时"能否剪得足够狠"直接决定算法是可行还是指数爆炸。

回溯框架代码：state、choices 与四个钩子

仓库将"尝试、回退、剪枝"提炼为如下通用框架（摘自 backtracking_algorithm.md，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) # 回退：撤销选择，恢复状态

框架中state表示当前状态（已做出的选择），choices表示当前状态下可做的选择。实现任何回溯题，只需四步：定义 state 与 choices，再分别实现is_solution、is_valid（剪枝）、make_choice/undo_choice（成对的尝试与回退）。仓库在 preorder_traversal_iii_template.py 中给出了基于该框架的完整模板实现，C++、Java、C#、Go、Swift、JS、TS、Dart、Rust、C、Kotlin、Ruby 等版本可分别在同章各语言目录下找到，例如 C++ 版目录、Java 版目录。框架代码还揭示了一个易错点：若题目要求"找到解后继续搜索所有解"，需删除记录解之后的return；主文档用动图对比了保留与删除return两种搜索过程的差异。

经典问题一：全排列——selected标记与哈希去重

全排列问题要求搜索给定集合所有可能的排列。小结给出的核心思路是：借助一个selected布尔数组记录每个元素是否已被选择，从而剪掉重复选择同一元素的分支，保证每个元素只被选一次。permutations_i.py 的实现完整呈现了这一设计：

def backtrack(state, choices, selected, res): 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对应selected[i] = False，state.append对应state.pop()，任何一侧遗漏都会破坏后续搜索的正确性（见 permutations_i.py 第 17-27 行）。

当集合中存在重复元素（如[1, 2, 2]）时，最终结果会出现重复排列。小结的解法是约束相等元素在每轮中只能被选择一次，实现上借助一个哈希集合：每轮循环开始时新建duplicated集合，选中某值后加入集合，同值的其他分支即被choice in duplicated剪掉。permutations_ii.py 中duplicated = set[int]()放在 for 循环内部是关键——它只在"同一层"内去重，跨层（不同位置）仍允许选相同值，这正是"每轮只能选一次"语义的精确落实。

经典问题二：子集和——排序 + start 起始点 + 相邻去重

子集和问题的目标是在集合中找到和为目标值的所有子集。这里有两类重复：

1. 顺序导致的重复：集合本身不区分元素顺序，但按任意顺序搜索会输出[4, 5]与[5, 4]这样的"同一子集"。小结给出的方案是回溯前先把数据排序，并设置一个变量（start）指示每一轮的遍历起始点——每选一个元素，下一轮只从它自身（或其后）继续，从结构上杜绝不同顺序产生同一子集。
2. 相等元素导致的重复：数组中的相等元素会生成完全相同的子集。利用"已排序"这一前置条件，判断相邻元素是否相等即可剪枝。

subset_sum_i.py 展示了前两项剪枝：nums.sort()提供排序前提，for i in range(start, len(choices))落实起始点约束，if target - choices[i] < 0: break则利用有序性提前终止——后边元素更大，子集和必然超标。升级到含重复元素的版本 subset_sum_ii.py 时，新增一条剪枝（第 25-26 行）：

# 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过 if i > start and choices[i] == choices[i - 1]: continue

i > start这个条件是精髓：它保证同一层的第一个相等元素仍可被选中（代表这一轮"选或不选该值"的分支起点），而后续同值元素全部跳过，从而确保相等元素每轮只被选中一次。对照 subset_sum_i_naive.py 中未做剪枝的朴素版本，可以更直观地看到剪枝前后的差异。

经典问题三：$n$ 皇后——四类约束与对角线索引规律

$n$ 皇后问题要求在 $n \times n$ 棋盘上放置 $n$ 个皇后使它们两两互不攻击，约束条件有四类：行约束、列约束、主对角线约束、次对角线约束。小结指出的处理策略是：

• 行约束：采用"按行放置"策略——每次只考虑当前行，天然保证每行恰有一个皇后，从而把 $n \times n$ 个格子的搜索压缩为 $n$ 轮、每轮 $n$ 个选择；
• 列约束：用一个数组记录每一列是否有皇后，指示当前格子是否合法；
• 对角线约束：借助两个数组分别记录主、次对角线上是否存在皇后。小结特别强调"难点在于找出处在同一主（副）对角线上的格子所满足的行列索引规律"。

这两条索引规律在 n_queens.py 第 25-26 行 中体现得一目了然：

diag1 = row - col + n - 1 # 主对角线：同一主对角线上 row - col 相同，加 n-1 使下标非负 diag2 = row + col # 次对角线：同一次对角线上 row + col 相同

对应地，辅助数组大小为[False] * n（列）与[False] * (2 * n - 1)（两类对角线各一条链）。放置时的剪枝判断、尝试与回退在 第 28-36 行 严格成对出现：

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 == n时说明所有行都已放置，深拷贝棋盘状态（[list(row) for row in state]）记为一个解——这个拷贝不可省略，否则后续回退会污染已记录的解。直接运行该脚本（如n = 4）会打印全部方案，可用于验证上述约束逻辑的正确性。

适用范围与局限性

小结对回溯算法的适用边界给出了明确判断：

• 搜索问题与约束满足问题是回溯的主战场，如全排列、子集和、$n$ 皇后、数独、图着色等；
• 组合优化问题虽然也能用回溯解决（如 0-1 背包、旅行商、最大团），但往往存在效率更高或效果更好的解法——0-1 背包通常用动态规划，旅行商常用遗传算法、蚁群算法等，最大团可用贪心等启发式算法。

局限性的根源在复杂度上：回溯通常需要遍历解空间的全部可能，时间复杂度可达指数阶或阶乘阶；空间上，递归调用要保存当前状态（路径、辅助标记等），搜索深度很大时空间需求也随之膨胀。即便如此，对于必须穷举的搜索与约束满足问题，回溯仍是标准解法，工程上的关键就是把前文所述的剪枝做足、把状态回退做对。

Q & A：怎么理解回溯和递归的关系？

原文档的 Q & A 给出的回答值得原样保留：总的来看，回溯是一种"算法策略"，而递归更像是一个"工具"。

• 回溯算法通常基于递归实现，但回溯是递归的应用场景之一，是递归在搜索问题中的应用；
• 递归的结构体现了"子问题分解"的解题范式，常用于解决分治、回溯、动态规划（记忆化递归）等问题。

用框架代码对照理解：backtrack函数对自身的每一次递归调用就是一次"尝试"的深入，而函数返回路径上的undo_choice完成"回退"——递归调用栈恰好充当了状态恢复的容器，这也解释了为什么尝试与回退必须严格成对：栈帧弹出时，现场必须与入栈前一致，下一轮遍历才能正确展开。

【免费下载链接】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