数据结构与算法 / 系统课时

剪枝与重复状态处理

剪枝与重复状态处理

回溯的性能瓶颈通常来自大量无效分支和重复答案。本课以“每个元素最多使用一次的组合求和”为主示例,说明何时可以安全剪枝,以及如何区分同层重复与路径内重复。

学习目标

  • 识别可以提前终止的无效分支
  • 使用排序完成可行性剪枝和同层去重
  • 理解剪枝成立所依赖的输入前提

剪枝必须有可证明的条件

可行性剪枝用于判断当前分支是否还可能满足约束。示例中的候选数全部为正数,排序后若 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,因为后续所有值都更大。修改剪枝后,应同时验证结果集合和递归调用次数,不能只看运行速度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

剪枝与重复状态处理

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通