Backtracking Algorithm in Hello Algo: Attempt, Backtrack and Pruning, from Preorder Traversal to a General Framework

2026-09-06 18:13:13作者：卓艾滢Kingsley

回溯算法（backtracking algorithm）是本仓库《Hello 算法》回溯章节的开篇核心内容：它是一种通过穷举解决搜索类问题的通用方法，从初始状态出发暴力搜索解空间，找到正确解即记录，直到找出全部解或穷尽所有可能。本文以"前序遍历二叉树"为例，逐步讲解回溯的三大支柱——尝试（attempt）、回退（backtrack）、剪枝（pruning），提炼出可复用于全排列、子集和、n 皇后等问题的通用框架代码，并总结其术语体系、优缺点与典型应用场景。读完本文，你将能理解回溯算法与深度优先搜索的关系，并把任一搜索问题映射到 "state / choices / res + 四个框架方法" 的标准求解流程中。

从前序遍历到一个搜索问题

回溯算法通常采用**深度优先搜索（depth-first search, DFS）**来遍历解空间。在二叉树章节中已经介绍过：前序、中序与后序遍历都属于深度优先搜索。下面借助前序遍历构造一个最简单的回溯问题，逐步观察回溯的工作原理。

!!! question "Example 1" 给定一棵二叉树，搜索并记录所有值为 $7$ 的节点，请返回节点列表。

解法非常直接：前序遍历整棵树，判断当前节点值是否为 $7$ ，若是则将该节点追加到结果列表 res。这里以 Python 实现为例（同一份逻辑在仓库各语言目录下均有对应实现，例如 C 版本、C++ 版本）：

def pre_order(root: TreeNode):
    """前序遍历：例题一"""
    if root is None:
        return
    if root.val == 7:
        # 记录解
        res.append(root)
    pre_order(root.left)
    pre_order(root.right)

可以看到，"访问每个节点"本身就是一次对解空间的探索，而 root is None 的返回（越过叶节点）以及递归调用结束后的 return（回到父节点）则构成了一次"回退"。下图展示了该树（层序 [1, 7, 3, 4, 5, 6, 7]）上前序遍历的访问顺序与目标节点的定位过程：

尝试与回退：理解 "前进" 与 "撤销"

回溯算法之所以得名，正是因为它采用"尝试"与"回退"两种互为逆向的策略：当搜索到达某个无法继续前进、或无法得到满足约束条件之解的状态时，算法撤销上一步的选择，退回上一状态，再尝试其他可能的分支。

仅凭例题一的代码，回退还只是简单的"函数返回"。需要强调的是，回退并不局限于函数返回——当我们需要携带"路径"这类可变状态时，回退还意味着状态的撤销。看例题二：

!!! question "Example 2" 在二叉树中搜索所有值为 $7$ 的节点，请返回根节点到这些节点的路径。

在例题一的基础上增加一个列表 path 记录访问路径。当访问到值为 $7$ 的节点时，复制 path 加入结果列表 res；而在每次回退前，把当前节点从 path 中弹出，以恢复本次尝试之前的状态。参考 preorder_traversal_ii_compact.py 的实现（以及 Java 版本、Go 版本）：

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()

root = list_to_tree([1, 7, 3, 4, 5, 6, 7])
path = list[TreeNode]()
res = list[list[TreeNode]]()
pre_order(root)
# 输出所有根节点到节点 7 的路径
for path in res:
    print([node.val for node in path])

仔细体会 path.append(root) 与 path.pop() 的对称位置：前者在递归进入子节点前执行（前进），后者在递归返回后执行（撤销）。二者被递归调用夹在中间、严格配对，这正是回溯能完整枚举所有根到目标节点路径的关键。对照下图中 11 步逐步推演可以更直观地看到：每当递归回溯一层，path 就同步缩短一次，实现与 DFS 状态完全同步的路径维护。

Step 1 ~ Step 11：前序遍历推进 → 记录解 → 弹出回退 → 换分支继续，交替进行，直至整棵树被穷尽。

剪枝：让约束条件帮我们砍掉无效分支

实际回溯问题通常带有若干约束条件（constraint），而约束正是剪枝的依据：

!!! question "Example 3" 在二叉树中搜索所有值为 $7$ 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 $3$ 的节点。

满足该约束只需在例题二的基础上加入一处"提前返回"：搜索时若遇到值为 $3$ 的节点，立刻剪枝，不再深入其子树。参考 preorder_traversal_iii_compact.py：

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

下图形象地展示了剪枝的效果：值为 $3$ 的节点被标红触发"提前返回"，其下方整棵子树（节点 $6$ 、 $7$ ）被灰色虚影遮罩，说明这些分支从未被实际访问——它们是被"剪掉"的无意义搜索空间。剪枝避免了大量无效尝试，是回溯算法效率提升的第一利器。

通用框架代码：尝试 / 回退 / 剪枝的抽象

例题一、二、三的代码本质相同，只是"解判定""合法性检查"各有差异。若将回溯的"尝试、回退、剪枝"主体提炼出来，即可得到一份高通用性的框架。框架中：

state 表示问题的当前状态（例如已访问的节点路径）；
choices 表示当前状态下可以做出的选择（例如当前节点的左右子节点）；
res 用于收集所有解。

核心模板代码如下（原始文档以多语言 Tab 展示，下面给出各语言对应实现；仓库内完整可运行版本见各语言的 preorder_traversal_iii_template 系列文件）。

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)

/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

/* 回溯算法框架 */
func backtrack(state *State, choices []Choice, res *[]State) {
    // 判断是否为解
    if isSolution(state) {
        // 记录解
        recordSolution(state, res)
        // 不再继续搜索
        return
    }
    // 遍历所有选择
    for _, choice := range choices {
        // 剪枝：判断选择是否合法
        if isValid(state, choice) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice)
            backtrack(state, choices, res)
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice)
        }
    }
}

/* Backtracking algorithm framework */
function backtrack(state, choices, res) {
    // Check if it is a solution
    if (isSolution(state)) {
        // Record the solution
        recordSolution(state, res);
        // Stop searching
        return;
    }
    // Traverse all choices
    for (let choice of choices) {
        // Pruning: check if the choice is valid
        if (isValid(state, choice)) {
            // Attempt: make a choice and update the state
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // Backtrack: undo the choice and restore to the previous state
            undoChoice(state, choice);
        }
    }
}

/* Backtracking algorithm framework */
void backtrack(State *state, Choice *choices, int numChoices, State *res, int numRes) {
    // Check if it is a solution
    if (isSolution(state)) {
        // Record the solution
        recordSolution(state, res, numRes);
        // Stop searching
        return;
    }
    // Traverse all choices
    for (int i = 0; i < numChoices; i++) {
        // Pruning: check if the choice is valid
        if (isValid(state, &choices[i])) {
            // Attempt: make a choice and update the state
            makeChoice(state, &choices[i]);
            backtrack(state, choices, numChoices, res, numRes);
            // Backtrack: undo the choice and restore to the previous state
            undoChoice(state, &choices[i]);
        }
    }
}

其余语言（C#、Swift、TypeScript、Dart、Rust、Kotlin、Ruby）的框架实现与上述逻辑一一对应，语法上仅在传参方式上略有差异，例如：

Swift 以 inout 传递 state 与 res（见 Swift 模板）；
Rust 使用 &mut State / &mut Vec<State>（见 Rust 模板）；
C 语言因无容器类型，额外用 numChoices/numRes 显式携带数组长度（见 C 模板）；
原始英文文档对每种语言都有完整框架代码：C++ / Java / C# / Go / Swift / JS / TS / Dart / Rust / C / Kotlin / Ruby，见 backtracking_algorithm.md。

框架之所以通用，是因为它只规定"何时递归、何时回退"的控制流，而把与具体问题相关的四件事留给调用者实现：

框架方法	职责	例题三中的对应实现
`is_solution(state)`	判断当前状态是否构成一个解	路径末端节点值为 $7$
`record_solution(state, res)`	记录解（注意拷贝，避免引用被后续修改）	将 `path` 的副本加入 `res`
`is_valid(state, choice)`	剪枝：判断选择是否合法	该节点非空且值不为 $3$
`make_choice` / `undo_choice`	尝试时更新状态 / 回退时恢复状态	`path.append(choice)` / `path.pop()`

在框架下求解例题三：一个值得注意的 return 细节

仓库中的 preorder_traversal_iii_template.py 用框架完整实现了例题三。该文件中 state 是节点遍历路径 path，choices 是当前节点的左右子节点（下一层递归时以 [choice.left, choice.right] 传入），res 收集路径列表：

def is_solution(state: list[TreeNode]) -> bool:
    """判断当前状态是否为解"""
    return state and state[-1].val == 7

def record_solution(state: list[TreeNode], res: list[list[TreeNode]]):
    """记录解"""
    res.append(list(state))

def is_valid(state: list[TreeNode], choice: TreeNode) -> bool:
    """判断在当前状态下，该选择是否合法"""
    return choice is not None and choice.val != 3

def make_choice(state: list[TreeNode], choice: TreeNode):
    """更新状态"""
    state.append(choice)

def undo_choice(state: list[TreeNode], choice: TreeNode):
    """恢复状态"""
    state.pop()

def backtrack(state: list[TreeNode], choices: list[TreeNode], res: list[list[TreeNode]]):
    """回溯算法：例题三"""
    # 检查是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
    # 遍历所有选择
    for choice in choices:
        # 剪枝：检查选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            # 进行下一轮选择
            backtrack(state, [choice.left, choice.right], res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

对比例题二的紧凑版 pre_order，这里出现了一个关键差异：在记录解之后，框架版没有 return，而是继续遍历其他选择。原因在于例题三要求返回"所有"满足条件的根到节点 $7$ 路径——找到一个值 $7$ 的节点后，其子树里可能还有别的值为 $7$ 的节点（例如树 [1, 7, 3, 4, 5, 6, 7] 中右子树末端还有一个 $7$ ），因此记录解后必须继续向下搜索。

下图左右对比了"保留 return"与"删除 return"两种写法的搜索过程差异：

保留 return：记录第一个解后立即终止该分支的递归，会漏掉同一路径或子树中后续的解；
删除 return：记录解后继续探索剩余子节点，才能枚举全部解。

由此可以总结出一个重要判据：到底在记录解后是否继续搜索，取决于题目要求的是"找一个解"还是"找所有解"——这也解释了为什么框架把"是否停止搜索"作为与问题绑定的决策点，而不是硬编码进模板。

相比基于前序遍历直写的紧凑代码，框架代码更啰嗦，但通用性显著更强：大量回溯问题都能直接套用该框架，只需按具体问题定义 state、choices 并实现上述四个方法即可。仓库中全排列、子集和、n 皇后等示例正是这套框架在不同问题上的实际落地。

常用术语：解、约束、状态、尝试、回退与剪枝

为了统一分析口径，下表汇总了回溯算法的常用术语定义，并对照例题三给出具体示例：

术语	定义	例题三中的对应物
解（solution）	满足问题特定条件的答案，可能有一个或多个	根节点到值为 $7$ 节点、且不含值为 $3$ 节点的所有路径
约束条件（constraint）	限制解可行性的条件，通常用于剪枝	路径中不包含值为 $3$ 的节点
状态（state）	问题在某一时刻的情况，包含已做出的选择	当前已访问的节点路径，即 `path` 节点列表
尝试（attempt）	依据可用选择探索解空间：做出选择、更新状态、检查是否为解	递归访问左/右子节点，将节点加入 `path`，判断节点值是否为 $7$
回退（backtracking）	遇到不满足约束的状态时，撤销先前选择回到上一状态	越过叶节点、结束节点访问、遇到值为 $3$ 的节点时终止搜索并函数返回
剪枝（pruning）	依据问题特性与约束避开无意义搜索路径的方法，可提高搜索效率	遇到值为 $3$ 的节点时不再继续向下搜索

提示：问题、解、状态等概念是跨算法通用的，在分治、回溯、动态规划、贪心等算法中均有涉及。

优点与局限性

回溯算法本质上是深度优先搜索 + 状态恢复，会尝试所有可能的解路径。它的优点在于能找出全部可行解，且在合理剪枝下效率很高；但面对大规模复杂问题，其运行效率可能难以接受：

时间维度：回溯通常需遍历状态空间的所有可能，最坏情况时间复杂度可达指数阶（如子集枚举 $O (2^{n})$ ）甚至阶乘阶（如全排列 $O (n!)$ ）；
空间维度：递归调用过程中需保存当前状态（路径、剪枝辅助变量等），搜索深度大时栈空间占用会急剧增长。

尽管如此，对某些搜索问题与约束满足问题，回溯仍是首选乃至唯一的系统性方案——因为无法预先判断哪些选择会通向有效解，只能遍历全部可能。这类场景下，优化效率的两条主线是：

剪枝（pruning）：在进入分支前就用约束判掉注定无解的子空间，同时节省时间与空间；
启发式搜索（heuristic search）：引入策略或估值函数，优先探索最可能产出有效解的分支。

回溯的典型应用

按问题目标的不同，回溯可解决的问题大致分三类（仓库 chapter_backtracking 目录对前几类均有对应源码实现）：

搜索问题——找出满足特定条件的所有解：

全排列问题：给定集合，求所有可能排列。对应示例 permutations_i.py（含重复元素的去重版本见 permutations_ii.py）；
子集和问题：给定集合与目标值，找出所有和为目标的子集，见 subset_sum_i.py 与去重版 subset_sum_ii.py；
汉诺塔问题：三柱挪盘、一次一盘、大不压小，见 hanota（该问题在分治章节也有讨论）。

约束满足问题——找到满足全部约束的解：

n 皇后问题： $n \times n$ 棋盘放置 $n$ 个互不攻击的皇后，实现见 n_queens.py；
数独： $9 \times 9$ 网格填 $1$ ~ $9$ ，使每行、每列与每个 $3 \times 3$ 子网格数字不重复；
图着色问题：无向图用最少颜色给顶点着色，使相邻顶点异色。

组合优化问题——在组合空间中寻找满足条件的最优解：

0-1 背包问题：容量限制下选择物品使总价值最大；
旅行商问题（TSP）：从一点出发遍历所有点恰好一次并返回起点的最短回路；
最大团问题：无向图中找最大的完全子图。

需要注意：对许多组合优化问题，回溯并非最优解法。例如 0-1 背包通常用动态规划获得更高时间效率；旅行商是著名的 NP-Hard 问题，常用遗传算法、蚁群算法等近似/启发式手段；最大团问题则可借助贪心等启发式算法求解。选型原则是：需要"全部解"或约束强、规模小时优先回溯；追求"最优解"且规模大时，应评估动态规划或专用启发式方法。

小结

从"前序遍历找节点"出发，本文完整还原了回溯算法的推导链：DFS 提供遍历骨架 → 路径维护带来"尝试/回退" → 约束条件引入"剪枝" → 提炼出 state / choices / res 通用框架。读者既可以对照三份紧凑版代码理解原理，也可以直接基于框架版代码，按 is_solution / record_solution / is_valid / make_choice / undo_choice 五个方法定制自己的回溯求解器——这正是后续排列问题、子集和问题与 n 皇后问题三篇实战文章共用的方法论基础。