LeetCode 40. 组合总和 II

约 6 分钟
文章信息 16 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 50-100 字节跳动 微软 美团 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 虾皮
标签
数组 回溯 回溯经典题 组合问题
目录

题目描述

✅ 40. 组合总和 II

image-20250419032428783

image-20250419032508705

题意分析

给定候选数组 candidates 和目标值 target，找出所有和为 target 的组合。两条规则缺一不可：候选数组里可能有重复数字，但每个位置上的数字最多只能用一次；结果集里不能出现重复的组合。

「不能重复」针对的是组合的值序列——[1, 7] 和 [7, 1] 算同一个组合，[1, 1, 6] 里的两个 1 来自不同下标是合法的，但两个不同下标的 1 各自单独和 7 配对，产生的两个 [1, 7] 只能保留一个。这是本题与「候选无重复、可无限复用」版本最本质的差别。

约束信号：candidates.length ≤ 100、candidates[i] ≤ 50、target ≤ 30，规模很小，指数级的搜索是出题人预期的解法；候选全是正数，意味着路径和只增不减，可以放心剪枝。

边界：不存在任何组合时返回空列表；target 恰好等于某个单独的候选数时，单元素组合也算。

解法：排序后回溯去重

核心思路

问题关键：每个下标只能使用一次，但数组中可能有重复值，结果又不能包含重复组合。真正需要解决的不是如何枚举，而是如何在搜索阶段去重。

为什么选排序 + 回溯：排序后，相同数字相邻，组合也天然按非递减顺序生成。递归从 start 往后选数，下一层传 i + 1，保证同一下标不会复用；候选都是正数，当前数大于剩余目标时可以直接结束本层。

不变量与正确性：dfs(start, remain) 中，path 只包含 start 之前已经选定的下标；本层每个值只作为当前位置的选择出现一次。条件 i > start && candidates[i] == candidates[i - 1] 只跳过同层重复，保留跨层选择两个相等元素的机会，因此不会漏掉 [1,1,6]，也不会重复生成 [1,7]。每条合法组合都有一条保留下来的唯一搜索路径。

解题步骤

  • 将数组升序排序，使重复值相邻，并为 break 剪枝提供单调性。
  • 定义 dfs(start, remain)：只从 [start, n) 选择下一项；remain == 0 时复制 path 加入答案。
  • 本层遇到与前一个候选相同的值时跳过，但必须满足 i > start，否则会误删跨层的合法重复值。
  • 若 candidates[i] > remain，后续数字只会更大，直接 break。
  • 选择 candidates[i] 后递归 dfs(i + 1, remain - candidates[i])，返回时撤销选择。
  • 以排序后的 [1,1,2,5,6,7,10] 为例：第一层第二个 1 被跳过；进入下一层后第二个 1 是该层首项，可以继续选择，因此既能得到 [1,1,6]，又不会重复得到 [1,7]。

代码实现

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> res) {
        if (remain == 0) {
            res.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]);
            dfs(candidates, remain - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    res := make([][]int, 0)
    path := make([]int, 0)

    var dfs func(int, int)
    dfs = func(start int, remain int) {
        if remain == 0 {
            combo := append([]int(nil), path...)
            res = append(res, combo)
            return
        }
        for i := start; i < len(candidates); i++ {
            if i > start && candidates[i] == candidates[i-1] {
                continue
            }
            if candidates[i] > remain {
                break
            }

            path = append(path, candidates[i])
            dfs(i+1, remain-candidates[i])
            path = path[:len(path)-1]
        }
    }

    dfs(0, target)
    return res
}

复杂度分析

  • 时间复杂度：排序为 $O(n \log n)$；搜索树最多有 $O(2^n)$ 个节点。若把复制答案的成本计入，设所有答案的元素总数为 $S$，总时间为 $O(n \log n + 2^n + S)$，最坏可写作 $O(n \cdot 2^n)$。
  • 空间复杂度：$O(n)$，来自递归栈与当前路径；不计返回结果本身。

关键点总结

  • 去重条件是 i > start && candidates[i] == candidates[i - 1]：同层去重，跨层放行。
  • 下一层传 i + 1 控制「每个下标只用一次」；第 39 题可复用元素，传的是 i。
  • 排序同时服务于相邻去重和正数剪枝，缺一不可。
  • 收集答案时必须复制 path，因为回溯会继续修改原列表。

易错点总结

  • 把条件写成 i > 0：[1,1,6]、target = 8 会误跳过第二层的 1，漏掉 [1,1,6]。
  • 递归仍传 i：[2,3]、target = 6 会非法生成 [2,2,2]；本题必须传 i + 1。
  • 答案不复制路径：直接加入 path 后，后续回溯会把已经保存的答案一起修改。
  • 未排序就去重或剪枝：重复值可能不相邻，break 也不再安全。
  • 把同层去重的 continue 写成 break：遇到第二个 1 就结束本层，会连后面的 [2,6] 也一起漏掉。

相似题目

题目 难度 考察点
39. 组合总和 中等 候选无重复且可无限复用，递归传 i，无需去重
77. 组合 中等 固定长度 k 的组合枚举，按剩余名额剪枝
216. 组合总和 III 中等 候选固定为 1–9 且限定个数，双重约束下的回溯
90. 子集 II 中等 同一套排序 + 同层去重，收集的是所有节点而非叶子
47. 全排列 II 中等 排列去重，用 visited 数组配合相邻相等判断
LCR 080. 组合 中等 77 题镜像，组合枚举的模板巩固
LCR 081. 组合总和 中等 39 题镜像，可复用元素的组合总和
LCR 082. 组合总和 II 中等 本题镜像，可作同一套代码的二次验证