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

用排序去重控制重复分支

用排序去重控制重复分支

含重复元素的回溯题,真正要去掉的不是“重复值”,而是会生成同一结果的等价分支。本篇用排序和层级边界区分同层去重、路径内再次使用与元素索引复用,最终形成一套可迁移到组合、子集和排列题的判断规则。

学习目标

  • 识别同层重复分支与路径中合法重复值的区别
  • 使用排序配合 start 或 used 正确去重
  • 根据题意决定下一层从 i 还是 i + 1 继续搜索

重复答案通常来自同层等价选择

设输入中有两个值都为 1。若它们在同一递归层承担完全相同的角色,那么“先选第一个 1”和“先选第二个 1”会展开出等价子树,保留两棵子树只会制造重复答案。

但路径中出现两个 1 不一定错误。例如数组里本来就有两个 1,题目又允许每个索引使用一次,那么先选第一个 1、进入下一层后再选第二个 1,表示使用了两个不同元素,应该保留。

同层去重与路径内重复使用的搜索树

用排序和层级边界建立去重规则

排序让相同值相邻,因此可以只比较当前元素和前一个元素。组合与子集通常使用 start 表示本层可以选择的起点,核心条件是 i > start && nums[i] == nums[i - 1]:只有“当前层的第二个及以后相同值”才跳过。

这里的 i > start 很重要。若写成 i > 0,就会把上一层已经选择过某个值的情况也误判为重复,从而删掉合法路径。

元素能否在同一路径中再次使用,是另一条独立规则。递归到 i + 1 表示当前索引最多使用一次;递归到 i 表示下一层还可以继续选择当前元素,常见于允许无限次复用候选数的题目。去重条件控制横向兄弟分支,递归起点控制纵向路径复用。

主示例:组合总和中的同层去重

下面实现经典的 Combination Sum II:数组可能含重复值,每个索引最多使用一次,要求返回所有和为目标值的不同组合。

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;

        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);

        System.out.println(result);
    }

    private static void backtrack(
            int[] candidates,
            int remain,
            int start,
            List<Integer> path,
            List<List<Integer>> result) {
        if (remain == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue; // 只跳过当前递归层中的等值兄弟分支
            }
            if (candidates[i] > remain) {
                break; // 已排序,后续元素只会更大
            }

            path.add(candidates[i]);
            backtrack(candidates, remain - candidates[i], i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

预期输出:

text
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

第一次在根层遇到值 1 时会进入递归;根层的第二个 1 因为 i > start 且与前一个值相同而被跳过。进入第一条 1 分支后,新的 start 已变化,此时另一个 1 不再属于“同层重复”,所以组合 [1, 1, 6] 能正常产生。

迁移到排列和子集

子集去重与组合几乎相同:先排序,再用 i > start 跳过当前层重复值。排列没有 start 单调右移,而是用 used[i] 记录当前路径已占用的索引;常见条件是 nums[i] == nums[i - 1] && !used[i - 1],表示前一个等值元素在本层还没被使用时,不再从后一个等值元素开启等价分支。

判断重复题时先问两个问题:当前分支和同层前一个分支是否会生成同一批结果,以及当前索引在更深路径中是否允许再次使用。 前者决定去重条件,后者决定递归边界;把这两件事分开,就不容易出现“去重过度”或“重复答案仍然存在”的错误。

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

目录与阅读设置

阅读设置

17

记录一个想法

用排序去重控制重复分支

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

登录哪都通