数据结构与算法 / 系统课时
剪枝与重复状态处理
剪枝与重复状态处理
回溯的性能瓶颈通常来自大量无效分支和重复答案。本课以“每个元素最多使用一次的组合求和”为主示例,说明何时可以安全剪枝,以及如何区分同层重复与路径内重复。
学习目标
- 识别可以提前终止的无效分支
- 使用排序完成可行性剪枝和同层去重
- 理解剪枝成立所依赖的输入前提
剪枝必须有可证明的条件
可行性剪枝用于判断当前分支是否还可能满足约束。示例中的候选数全部为正数,排序后若 candidate > remaining,后面的数只会更大,因此可以直接 break。
最优性剪枝用于最优化问题。若“当前成本 + 理论最小剩余成本”已经不可能优于现有最优解,也可以停止该分支。无论哪种剪枝,都必须证明被跳过的分支不会产生新答案。

同层重复与路径内重复
排序后,相同值相邻。组合问题的经典同层去重条件是 i > start && candidates[i] == candidates[i - 1]。其中 i > start 表示当前元素不是本层第一个候选,只跳过同一父状态下的后续重复值。
不能把条件写成 i > 0,否则深层可能无法选择第二个相同值,例如合法答案 [1,1,6] 会被错误删除。
路径内重复由递归参数 i + 1 控制,表示同一个数组下标最多使用一次。它与“同一层不要从等值候选开始重复分支”解决的是两个不同问题。
主示例:组合求和与去重
下面的 Java 17 程序要求候选数均为正数。排序既服务于相邻去重,也保证 candidate > remaining 时可以安全使用 break。
java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PruningAndDeduplicationDemo {
public static void main(String[] args) {
int[] candidates = {10, 1, 2, 7, 6, 1, 5};
int target = 8;
List<List<Integer>> result =
combinationSumOnce(candidates, target);
System.out.println("sorted = " + Arrays.toString(candidates));
System.out.println("result = " + result);
}
public static List<List<Integer>> combinationSumOnce(
int[] candidates,
int target
) {
if (candidates == null) {
throw new IllegalArgumentException(
"candidates must not be null"
);
}
if (target < 0) {
throw new IllegalArgumentException(
"target must not be negative"
);
}
for (int candidate : candidates) {
if (candidate <= 0) {
throw new IllegalArgumentException(
"all candidates must be positive"
);
}
}
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(
candidates, target, 0, new ArrayList<>(), result
);
return result;
}
private static void backtrack(
int[] candidates,
int remaining,
int start,
List<Integer> path,
List<List<Integer>> result
) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// 同一决策层只保留一个相同起点。
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
int candidate = candidates[i];
if (candidate > remaining) {
break;
}
path.add(candidate);
backtrack(
candidates,
remaining - candidate,
i + 1,
path,
result
);
path.remove(path.size() - 1);
}
}
}预期输出:
text
sorted = [1, 1, 2, 5, 6, 7, 10]
result = [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]剪枝边界与验证
break 的成立依赖两个前提:数组已经升序排列,候选值全部为正数。若允许负数,较大的当前值之后仍可能出现负数把总和降回目标,此时该剪枝不再正确。
重复值只需要 continue 当前候选,因为后面可能出现新的不同值;超过剩余目标则应 break,因为后续所有值都更大。修改剪枝后,应同时验证结果集合和递归调用次数,不能只看运行速度。
按自己的节奏,确认真正理解。