13.1 回溯算法

「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态
出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择
都无法找到解为止。

回溯算法通常采用“深度优先搜索”来遍历解空间。在二叉树章节中，我们提到前序、中序和后序遍历都属
于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。

b
例题一

给定一个二叉树，搜索并记录所有值为 7 的节点，请返回节点列表。

对于此题，我们前序遍历这颗树，并判断当前节点的值是否为 7 ，若是则将该节点的值加入到结果列表 res
之中。相关过程实现如图 13‑1 和以下代码所示。

// === File: preorder_traversal_i_compact.c ===
/* 前序遍历：例题一 */
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
if (root->val == 7) {
// 记录解
res[resSize++] = root;
}
preOrder(root->left);
preOrder(root->right);
}

13.1.1 尝试与回退

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过
程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，
并尝试其他可能的选择。
对于例题一，访问每个节点都代表一次“尝试”，而越过叶节点或返回父节点的 return 则表示“回退”。
值得说明的是，回退并不仅仅包括函数返回。为解释这一点，我们对例题一稍作拓展。

b

例题二

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

在例题一代码的基础上，我们需要借助一个列表 path 记录访问过的节点路径。当访问到值为 7 的节点时，则
复制 path 并添加进结果列表 res 。遍历完成后，res 中保存的就是所有的解。

// === File: preorder_traversal_ii_compact.c ===
/* 前序遍历：例题二 */
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
// 尝试
path[pathSize++] = root;
if (root->val == 7) {
// 记录解
for (int i = 0; i < pathSize; ++i) {
res[resSize][i] = path[i];
}
resSize++;
}
preOrder(root->left);
preOrder(root->right);
// 回退
pathSize--;
}

在每次“尝试”中，我们通过将当前节点添加进 path 来记录路径；而在“回退”前，我们需要将该节点从
path 中弹出，以恢复本次尝试之前的状态。

观察图 13‑2 所示的过程，我们可以将尝试和回退理解为“前进”与“撤销”，两个操作是互为逆向的。

13.1.2 剪枝

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。

b
例题三

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

为了满足以上约束条件，我们需要添加剪枝操作：在搜索过程中，若遇到值为 3 的节点，则提前返回，停止
继续搜索。

// === File: preorder_traversal_iii_compact.c ===
/* 前序遍历：例题三 */
void preOrder(TreeNode *root) {
// 剪枝
if (root == NULL || root->val == 3) {
return;
}
// 尝试
path[pathSize++] = root;
if (root->val == 7) {
// 记录解
for (int i = 0; i < pathSize; i++) {
res[resSize][i] = path[i];
}
resSize++;
}
preOrder(root->left);
preOrder(root->right);
// 回退
pathSize--;
}

剪枝是一个非常形象的名词。如图 13‑3 所示，在搜索过程中，我们“剪掉”了不满足约束条件的搜索分支，
避免许多无意义的尝试，从而提高了搜索效率。

13.1.3 框架代码

接下来，我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来，提升代码的通用性。

在以下框架代码中，state 表示问题的当前状态，choices 表示当前状态下可以做出的选择。

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

接下来，我们基于框架代码来解决例题三。状态 state 为节点遍历路径，选择 choices 为当前节点的左子节
点和右子节点，结果 res 是路径列表。

// === File: preorder_traversal_iii_template.c ===
/* 判断当前状态是否为解 */
bool isSolution(void) {
return pathSize > 0 && path[pathSize - 1]->val == 7;
}
/* 记录解 */
void recordSolution(void) {
for (int i = 0; i < pathSize; i++) {
res[resSize][i] = path[i];
}
resSize++;
}
/* 判断在当前状态下，该选择是否合法 */
bool isValid(TreeNode *choice) {
return choice != NULL && choice->val != 3;
}
/* 更新状态 */
void makeChoice(TreeNode *choice) {
path[pathSize++] = choice;
}
/* 恢复状态 */
void undoChoice(void) {
pathSize--;
}
/* 回溯算法：例题三 */
void backtrack(TreeNode *choices[2]) {
// 检查是否为解
if (isSolution()) {
// 记录解
recordSolution();
}
// 遍历所有选择
for (int i = 0; i < 2; i++) {
TreeNode *choice = choices[i];
// 剪枝：检查选择是否合法
if (isValid(choice)) {
// 尝试：做出选择，更新状态
makeChoice(choice);
// 进行下一轮选择
TreeNode *nextChoices[2] = {choice->left, choice->right};
backtrack(nextChoices);
// 回退：撤销选择，恢复到之前的状态
undoChoice();
}
}
}

根据题意，我们在找到值为 7 的节点后应该继续搜索，因此需要将记录解之后的 return 语句删除。图 13‑4
对比了保留或删除 return 语句的搜索过程。

相比基于前序遍历的代码实现，基于回溯算法框架的代码实现虽然显得啰嗦，但通用性更好。实际上，许多
回溯问题都可以在该框架下解决。我们只需根据具体问题来定义 state 和 choices ，并实现框架中的各个方法即可。

13.1.4 常用术语

为了更清晰地分析算法问题，我们总结一下回溯算法中常用术语的含义，并对照例题三给出对应示例
。

表 13‑1 常见的回溯算法术语
名词 定义 例题三

解 Solution 解是满足问题特定条件的答案，可能有一个或
多个
根节点到节点 7 的满足约束条件的所有路
径

约束条件
Constraint
约束条件是问题中限制解的可行性的条件，通
常用于剪枝
路径中不包含节点 3
状态 State 状态表示问题在某一时刻的情况，包括已经做
出的选择
当前已访问的节点路径，即 path 节点列表

尝试
Attempt
尝试是根据可用选择来探索解空间的过程，包
括做出选择，更新状态，检查是否为解
递归访问左（右）子节点，将节点添加进
path ，判断节点的值是否为 7

回退
Backtracking
回退指遇到不满足约束条件的状态时，撤销前
面做出的选择，回到上一个状态
当越过叶节点、结束节点访问、遇到值为 3
的节点时终止搜索，函数返回

名词 定义 例题三

剪枝
Pruning
剪枝是根据问题特性和约束条件避免无意义的
搜索路径的方法，可提高搜索效率
当遇到值为 3 的节点时，则终止继续搜索

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

13.1.5 优势与局限性

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的
优势在于它能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。

然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。

‧ 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。

‧ 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间
需求可能会变得很大。

即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪
些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何进行效率优
化，常见的效率优化方法有两种。

‧ 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。

‧ 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。

13.1.6 回溯典型例题

回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题。

搜索问题：这类问题的目标是找到满足特定条件的解决方案。

‧ 全排列问题：给定一个集合，求出其所有可能的排列组合。

‧ 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集。

‧ 汉诺塔问题：给定三个柱子和一系列大小不同的圆盘，要求将所有圆盘从一个柱子移动到另一个柱子，
每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上。

约束满足问题：这类问题的目标是找到满足所有约束条件的解。

‧