13.1 回溯算法
回溯算法（Backtracking Algorithm）是一种通过穷举所有可能的解决方案来解决问题的方法。其核心思想是从一个初始状态出发，逐步尝试所有可能的选择，并在遇到符合条件的解时记录下来。如果尝试了所有可能的选择仍无法找到解，算法将停止。
回溯算法通常采用“深度优先搜索”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们通过前序遍历构造一个回溯问题，逐步理解回溯算法的工作原理。
例题一
给定一棵二叉树，搜索并记录所有值为指定目标值的节点，并返回这些节点的列表。
我们使用前序遍历这棵树，并判断当前节点的值是否为目标值。如果是，则将该节点加入结果列表 res 中。以下是实现代码：
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)
在该例题中，前序遍历的每次节点访问都代表一次“尝试”，而当遍历结束或返回到父节点时则表示“回退”。
13.1.1 尝试与回退
回溯算法之所以得名，是因为该算法在搜索解空间时采用了“尝试”与“回退”的策略。当遇到无法继续前进或无法满足条件的解时，算法会撤销上一步的选择，退回到先前的状态，并尝试其他可能的选择。
例题二 在二叉树中搜索所有值为目标值的节点，并返回从根节点到这些节点的路径。
在前序遍历的基础上，我们需要一个列表 path 来记录当前的路径。当访问到值为目标值的节点时，将路径的副本添加到结果列表 res 中。以下是实现代码：
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()
在每次“尝试”中，当前节点被添加进 path 以记录路径；在“回退”之前，该节点被从 path 中移除，恢复到本次尝试之前的状态。
13.1.2 剪枝
复杂的回溯问题通常包含一个或多个约束条件，这些条件可以用来“剪枝”。
例题三 在二叉树中搜索所有值为目标值的节点，并返回根节点到这些节点的路径，同时路径中不能包含某特定值。
为满足约束条件，我们需要添加剪枝操作：在搜索过程中，若遇到特定值的节点，则提前返回，不再继续搜索。以下是实现代码：
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()
“剪枝”是一个非常形象的概念。在搜索过程中，我们“剪掉”不满足约束条件的搜索分支，从而避免许多无意义的尝试，提高搜索效率。
13.1.3 回溯算法框架代码
我们可以将回溯的“尝试、回退、剪枝”抽象为框架代码，以提升代码的通用性。以下是框架代码示例：
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 为当前节点的左、右子节点，结果 res 为路径列表。此框架虽然显得繁琐，但具有较好的通用性，适用于很多回溯问题。
13.1.4 常用术语
为了更清晰地分析回溯算法，我们总结了一些常用术语及其定义，并给出例题三中的对应示例：
| 名词 | 定义 | 例题三 |
|---|---|---|
| 解 (Solution) | 满足问题特定条件的答案，可能有一个或多个 | 从根节点到目标节点的路径 |
| 约束条件 (Constraint) | 限制解的可行性的条件，通常用于剪枝 | 路径中不包含特定值的节点 |
| 状态 (State) | 问题在某一时刻的情况，包括已做出的选择 | 当前已访问的节点路径，即 path 节点列表 |
| 尝试 (Attempt) | 探索解空间的过程，包括做出选择、更新状态、检查解 | 递归访问左右子节点，将节点添加进 path，判断值 |
| 回退 (Backtracking) | 遇到不满足条件的状态时，撤销前面选择，回到上一个状态 | 当访问结束或遇到剪枝条件时，终止搜索，函数返回 |
| 剪枝 (Pruning) | 避免无意义的搜索路径，提高效率 | 遇到特定值节点时，不再继续搜索 |
13.1.5 优点与局限性
回溯算法是深度优先搜索算法的一种，尝试所有可能的解直到找到满足条件的解。其优点在于能够找到所有可能的解，且在合理剪枝的情况下具有较高的效率。然而，回溯算法在处理大规模或复杂问题时，运行效率可能较低。
- 时间复杂度：回溯算法通常需要遍历所有可能状态，时间复杂度可能达到指数或阶乘级别。
- 空间复杂度：在递归调用中需要保存当前状态（如路径），深度较大时空间需求可能会很大。
尽管如此，回溯算法在一些搜索和约束满足问题中仍是最佳解决方案。优化回溯算法的常用方法包括剪枝和启发式搜索。
13.1.6 回溯算法典型例题
回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题：
- 搜索问题：目标是找到满足特定条件的解，如全排列问题、子集和问题、汉诺塔问题。
- 约束满足问题：目标是找到满足所有约束条件的解，如八皇后问题、数独、图着色问题。
- 组合优化问题：目标是在组合空间中找到满足某些条件的最优解，如0-1背包问题、旅行商问题、最大团问题。
请注意，对于许多组合优化问题，回溯并不是最优解决方案。例如，0-1背包问题常用动态规划，旅行商问题常用遗传算法或蚁群算法，而最大团问题可用贪心算法等启发式算法解决。
