【算法】回溯算法精讲：从深度优先搜索到剪枝优化​

导读

大家好，很高兴又和大家见面啦！！！

在前面探讨递归算法的基础上，我们今天将进一步深入这一重要编程思想的应用领域。

递归通过函数自我调用将复杂问题分解，其核心思想与深度优先遍历（DFS）“一路到底，再回溯而上”的策略天然契合。DFS作为递归在树与图等数据结构中的经典体现，为我们理解更复杂的算法范式奠定了坚实基础。

接下来，我们将一同探索一种在DFS基础上增强的、更为强大的算法思想——回溯算法。它将带领我们系统性地遍历问题的所有可能解，并学习如何通过有效的“剪枝”来优化搜索过程。

现在，让我们直接进入正文，开启这段探索之旅。

一、回溯

1.1 定义

回溯法是一种通过系统性地、深度优先地遍历状态空间树来搜索问题所有可能解的算法范式。

适用范围：回溯法适用于那些需要检查大量可能组合的组合优化问题和决策问题。

1.2 核心要点

状态空间树：​ 问题的解可以被表示为一棵树，称为状态空间树或解空间树。

• 树的每个节点代表问题求解过程中的一个部分解或一个状态。
• 树的边代表一个决策步骤，即从父节点的状态通过一个选择转移到子节点的状态。
• 树的根节点代表初始状态（空解）。
• 树的叶子节点代表终结状态，可能是一个完整解，也可能是一个无效的解。

flowchart TB
	subgraph Tree[空间状态树]
		direction TB
		begin[开始]
		a[状态1]
		b[状态2]
		c[状态3]
		begin--->a
		begin--->b
		begin--->c
		d[...]
		e[...]
		f[...]
		a--->d
		b--->e
		c--->f
		g[最终状态]
		h[最终状态]
		i[最终状态]
		d--->g
		e--->h
		f--->i
	end

深度优先搜索：​ 回溯法以深度优先的顺序遍历这棵状态空间树。

• 它从根节点开始，沿着一条路径一直向下扩展，直到达到一个叶子节点或确定当前分支无法产生有效解。

隐式图搜索：​ 回溯法并不需要事先在内存中构建整棵状态空间树（这通常是指数级大小的，不可能完成）。

• 树是“隐式”存在的，算法在运行过程中只维护当前正在探索的路径。

回退操作：​ 这是回溯法的标志性操作。当算法到达一个节点，确定从该节点出发无法找到有效解时（即该节点及其子树不包含可行解），它会撤销最近做出的选择，回退到父节点，并尝试父节点状态下的下一个可选分支。

二、剪枝

2.1 定义

剪枝是一种用于优化搜索过程（如回溯法、分支限界法）的技术。

核心思想：在状态空间树的遍历过程中，提前识别并跳过那些不可能产生最优解或可行解的分支，从而减少需要实际探索的节点数量。

2.2 核心要点

目标：​ 显著降低算法的时间复杂度。虽然最坏情况下的时间复杂度可能仍是指数级，但通过剪枝，平均情况下的运行时间会得到极大改善，使得解决规模较大的问题成为可能。

约束函数：​ 这是实现剪枝的主要工具。它是一个判断函数，在搜索过程中，当扩展一个节点（生成子节点）之前或之后，用约束函数来检查该节点所代表的部分解。

• 如果约束函数返回“假”：意味着从当前部分解继续扩展，不可能得到任何满足问题约束条件的可行解。因此，算法可以立即停止探索以该节点为根的整个子树。这个过程就是“剪枝”。

限界函数：​ 在优化问题（如旅行商问题、0-1背包问题）中，除了约束函数，还会使用限界函数进行剪枝。限界函数计算当前节点可能达到的最好结果（上界/下界）。

• 如果这个“可能的最好结果”已经比当前已知的某个完整解还要差，那么继续探索该分支就没有意义，可以将其剪掉。这通常与分支限界法结合得更紧密，但思想相通。

剪枝不是一个独立的算法，而是一种嵌入在搜索算法中的优化策略。

三、个人理解

回溯算法 可以简单的理解为：在 深度优先搜索 的过程中，从一个节点回退到其父节点的操作；

剪枝 则可以理解为：在 搜索 算法的过程中，若当前满足某一条件，则跳过当前的搜索对象的操作；

为了方便大家进一步理解这两个概念，下面我们以获取 1/2/3 这三个数的全部排列为例来进行说明：

当我们要获取三位数的全排列时，我们可以将问题分成3部分：

• 第一位数：从三个数中选择一个
• 第二位数：从剩下的两个数中选择一个
• 第三位数：从剩下的一个数中选择一个

如果我们将这一过程以树的形式进行展示的话，我们就会得到这么一棵树：

flowchart TB
begin[开始]
	subgraph A[第一位数]
		direction TB
		a[1]
		b[2]
		c[3]
	end
begin--->a
begin--->b
begin--->c
	subgraph B[第二位数]
		direction TB
		subgraph B1[情况1]
			d1[1]
			e1[2]
			f1[3]
		end
		subgraph B2[情况2]
			d2[1]
			e2[2]
			f2[3]
		end
		subgraph B3[情况3]
			d3[1]
			e3[2]
			f3[3]
		end
	end
	subgraph C[第三位数]
		direction TB
		subgraph C1[情况1]
			g1[1]
			h1[2]
			i1[3]
		end
		subgraph C2[情况2]
			g2[1]
			h2[2]
			i2[3]
		end
		subgraph C3[情况3]
			g3[1]
			h3[2]
			i3[3]
		end
		subgraph C4[情况4]
			g4[1]
			h4[2]
			i4[3]
		end
		subgraph C5[情况5]
			g5[1]
			h5[2]
			i5[3]
		end
		subgraph C6[情况6]
			g6[1]
			h6[2]
			i6[3]
		end
	end
	a --->e1
	a--->f1
	b--->d2
	b--->f2
	c--->d3
	c--->e3
	e1--->i1
	f1 ---> h2
	d2 --->i3
	f2 --->g4
	d3 ---> h5
	e3 ---> g6

若我们不做任何处理的情况下，这三位数在进行选择时，每一位上的数都会存在3种选择，这里我们以获取第一种排列：123 为例：

flowchart TB
	subgraph A[第一位数]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位数]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	subgraph C[第三位数]
		direction TB
		g1[1]
		h1[2]
		i1[3]
	end
	A--->B--->C

第一位数我们选择 1 ，那么在选择第二位数时，我们在不做任何处理的情况下，我们同样会选择 1：

flowchart TB
	subgraph A[第一位数]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位数]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	a ---> d1

但是 1 已经在第一位数中被选择，因此我们在选择第二位数时，就无法选择 1 这时的搜索过程我们就无需向下继续搜索，按照 深度优先搜索 的搜索过程，这时我们会从该节点返回到其父节点；

在这个过程中，就同时涉及 回溯 与 剪枝：

• 从第二位数 1 这个节点返回到第一位数 1 这个父节点的过程就是 回溯

flowchart BT
	subgraph A[第一位数]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位数]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	d1 --->|回溯|a

• 我们舍弃掉第二位数 1 这条路径的过程就是 剪枝

flowchart TB
	subgraph A[第一位数]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位数]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	a --->|剪枝<br>舍弃该路径<br>|d1

从树的角度来看，树中的每一条路径都是树的一根枝叶，而我们舍弃路径的行为就类似于修剪树的枝叶，因此将该过程称为 剪枝 还是十分形象的。

四、代码解释

这里我们就以【LeetCode】专栏中的一道题：【LeetCode】组合问题——1863.找出所有子集的异或总和再求和（回溯）中的代码为例进行说明，完整代码如下所示：

void Subset(int* nums, int numsSize, int* ans, int* mid, int start) {
	*ans += *mid;
	for (int i = start; i < numsSize; i++) {
		*mid ^= nums[i];
		Subset(nums, numsSize, ans, mid, i + 1);
		*mid ^= nums[i];
	}
}

int subsetXORSum(int* nums, int numsSize) {
	int ans = 0, mid = 0;
	Subset(nums, numsSize, &ans, &mid, 0);
	return ans;
}

这里的 Subset 函数就是通过递归实现的查找子集并获取子集的异或和的总和。

4.1 回溯

代码中有两次 *mid ^= nums[i] ：

• 第一次是获取子集的异或和
• 第二次是借助异或的规则：a ^ b ^ b = a 来进行 回溯

简单的来说，对于数组 [1,2,3] 其子集按照起始元素可以分为三类：

• [1]、[1, 2]、[1, 3]、[1, 2, 3]
• [2]、[2, 3]
• [3]

对于子集 [1, 2] 和 [1, 3] 而言，他们的起始元素均为 1 。当我们通过路径：1--->2--->3 完成子集的异或以及求取 [1]、[1, 2]、[1, 2, 3] 这三个子集的异或和的总和之后，函数会开始回归；

当函数从节点 3 回归到父节点 2 时，mid 进行了一次异或操作，由原先的 *mid = 0 ^ 1 ^ 2 ^ 3 再一次异或了一个 3 于是就得到了 mid = 0 ^ 1 ^ 2 ^ 3 ^ 3 = 0 ^ 1 ^ 2，即，当函数回归到节点 2 时，此时的 mid 中存放的值为：*mid = 0 ^ 1 ^ 2 ；

也就是说，当我们探索相同父节点的不同分支对应的子集时，我们需要将 mid 中存储的值从子集的异或值 回溯 到其父节点的异或值，在上面的实现中，就是通过第二次的异或操作实现 回溯 这一过程；

4.2 剪枝

在该函数实现中，我们是通过循环来找到同一父节点的不同分支，而循环的结束条件 i < numsSize 作为 界限函数 进行了一次 剪枝 操作，将不符合该范围的枝叶全部剪掉；

循环的对象 i = start 以及父节点的传参中 i + 1 作为 约束函数 同样也执行了一次 剪枝 操作，该 约束函数 将下标 i 左侧以及它本身的所有元素对应的枝叶全部剪掉；

通过这两次 剪枝 操作，使得 Subset 函数能够更加高效的查找子集并获取子集的异或和以及所有子集的异或和的总和；

结语

通过本篇的探讨，我们系统性地解析了回溯算法的核心思想与实现机制。回溯法作为一种通过深度优先策略遍历状态空间树的算法框架，其本质在于“试探与回退”的智能搜索过程 。

✨ 核心要点回顾

• 回溯与剪枝的协同是提升算法效率的关键。
  • 回溯负责在路径无效时撤销选择并回退
  • 剪枝则通过约束函数和界限函数提前排除不可能产生解的分支
  • 二者结合能显著减少不必要的计算。
• 从全排列问题的实例推演，到子集异或和计算的代码剖析，我们看到回溯算法通过“选择-递归-撤销”的通用模式解决各类组合优化问题。
• 理解回溯与深度优先搜索（DFS）的关系至关重要：回溯算法是对深度优先搜索的增强，通过引入状态回退和剪枝逻辑，使其能够高效处理组合爆炸问题。

回溯算法不仅是一种强大的编程工具，其核心的“试错-回退-剪枝”思想，也为我们提供了一种解决复杂问题的系统性方法论：勇于尝试，善于调整，懂得取舍。

在接下来的内容中，我们将通过一系列 LeetCode习题，继续深入探讨回溯算法在更复杂场景下的应用与实践。大家记得关注哦！

互动话题：在学习回溯算法的过程中，你是否也联想到了生活中哪些“试探、调整与优化”的经历呢？欢迎在评论区分享你的故事！

互动与分享

• 点赞👍 - 您的认可是我持续创作的最大动力
• 收藏⭐ - 方便随时回顾这些重要的基础概念
• 转发↗️ - 分享给更多可能需要的朋友
• 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！