数据结构与算法 / 系统课时
用剪枝提前终止无效搜索
用剪枝提前终止无效搜索
回溯的性能取决于搜索树里有多少节点真正被展开。剪枝的目标不是改变答案,而是在能够证明某个子树不可能产生解时立刻停止。本篇从剩余容量、排序界限和可行性上下界三类条件入手,建立安全剪枝的判断顺序。
学习目标
- 根据剩余容量和候选范围识别必然无解的子树
- 利用排序把“跳过当前值”升级为“终止后续枚举”
- 用可达到的最小值与最大值证明剪枝条件不会漏解
剪枝必须建立在“不可能成功”的证明上
回溯通常先做选择,再递归验证。如果某个状态已经无法满足目标,却仍继续向下搜索,就会产生大量无意义节点。安全剪枝要求条件具有单调性或明确的可行性边界:一旦条件触发,当前子树中的所有后代都不可能成为答案。
常见依据有三类:剩余目标已经小于当前候选;排序后后续候选只会更大;剩余槽位即使取最小可用值仍超过目标,或即使取最大可用值也达不到目标。前两类适合在循环内尽早 break,第三类适合在递归入口直接 return。

先做便宜且单调的判断
剪枝顺序应优先放成本低、判断明确的条件。例如候选数组已经升序,且所有数均为正数,当 candidate > remain 时,当前值无法选择,后面的值更大,也同样无法选择,所以应该 break 而不是 continue。
若题目要求还要选择固定数量的元素,可以继续计算可达区间。假设还需选 slots 个数,则当前状态至少会增加某个最小和,至多会增加某个最大和。若 remain 不在这个区间内,整棵子树都无解,可以在进入循环前返回。
主示例:用上下界剪掉不可能的组合
下面从 1 到 9 中选择 k 个互不重复且递增的数字,使其总和等于目标值。递归入口先检查剩余可选数量,再计算当前状态能达到的最小和与最大和。
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
int k = 3;
int target = 9;
List<List<Integer>> result = new ArrayList<>();
backtrack(1, k, target, new ArrayList<>(), result);
System.out.println(result);
}
private static void backtrack(
int next,
int slots,
int remain,
List<Integer> path,
List<List<Integer>> result) {
if (slots == 0) {
if (remain == 0) {
result.add(new ArrayList<>(path));
}
return;
}
if (10 - next < slots) {
return; // 剩余数字数量不足,无法填满槽位
}
int minSum = 0;
for (int i = 0; i < slots; i++) {
minSum += next + i;
}
int maxSum = 0;
for (int value = 9; value >= 10 - slots; value--) {
maxSum += value;
}
if (remain < minSum || remain > maxSum) {
return; // 目标不在当前状态的可达区间内
}
for (int value = next; value <= 9; value++) {
if (value > remain) {
break; // 候选递增且均为正数,后续值同样过大
}
if (10 - value < slots) {
break; // 连当前值在内也凑不够 slots 个数字
}
path.add(value);
backtrack(value + 1, slots - 1, remain - value, path, result);
path.remove(path.size() - 1);
}
}
}预期输出:
[[1, 2, 6], [1, 3, 5], [2, 3, 4]]例如某个状态还要选择 2 个数,而从当前起点能取得的两个最小值之和已经大于 remain,继续向下只会让总和更大,因此可以直接返回。反过来,如果两个最大可用值之和仍小于 remain,也没有继续搜索的意义。
判断该用 return、break 还是 continue
return 用于证明“整个当前状态都无解”;break 用于有序枚举中证明“当前候选以及后续候选都无解”;continue 只表示“当前候选无效,但后面的候选仍可能有效”。三者选错会直接影响正确性。
写剪枝时最好先写出未经剪枝仍能得到正确答案的版本,再逐条加入能够证明安全的条件,并用相同测试用例比对结果集合。剪枝通常显著减少实际访问节点,但最坏情况下回溯仍可能是指数复杂度,因此评价优化时应同时看正确性、访问节点数量和输入约束,而不是把剪枝误认为改变了问题的理论复杂度。