LeetCode LCR 082. 组合总和 II

约 5 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 回溯

题目描述

✅ LCR 082. 组合总和 II

image-20260929005927850

image-20260929005927851

题意分析

从可能含重复值的正整数数组中选出和为 target 的所有组合。每个输入位置最多使用一次，答案中相同的值组合也只能出现一次。

这两个限制要分别处理：不能复用同一下标，但可以使用不同位置上的相同值；也不能因选择了不同的同值位置，就把相同组合重复输出。

解法：排序与同层去重回溯

核心思路

[!blue]

先排序，使相同值相邻。用 u 表示本层最小可选下标，s 表示路径和，t 保存路径。选中下标 i 后递归到 i + 1，保证下标严格递增，既不复用位置，也不生成同一批位置的不同排列。

仅让下标递增仍可能选出相同的值组合。因此本层遇到 i > u && candidates[i] == candidates[i - 1] 时跳过：若改用前一个相同值，后面这些位置仍然都能选，所以当前分支能生成的值组合，已经被前一个同值分支覆盖。

去重只发生在同一层。i == u 是本层第一次可选的位置，即使它与前一个位置同值，也要保留；前一个位置可能已经由上一层选中，此时继续选择另一份相同值是合法的。不能把整个数组的重复值删掉。

s == target 时保存副本并返回；s > target 时直接返回，因为所有数为正，不可能再把和减回目标。每次递归返回后撤销路径末项，恢复同层下一分支的起点状态。

解题步骤

  1. 对候选数组排序，初始化结果，从 u = 0、s = 0 和空路径开始。
  2. 超过目标就返回；达到目标则保存路径副本后返回。
  3. 从 u 开始枚举下标，跳过本层已经尝试过的相同值。
  4. 加入当前元素，递归到 i + 1，并更新路径和。
  5. 返回后删除末项，继续枚举，最后返回全部组合。

代码实现

class Solution {
    private List<List<Integer>> answer;
    private int[] candidates;
    private int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        answer = new ArrayList<>();
        // 排序让相同值相邻，是同层去重条件成立的前提。
        Arrays.sort(candidates);
        this.target = target;
        this.candidates = candidates;
        dfs(0, 0, new ArrayList<>());

        return answer;
    }

    // u：本层允许选取的最小下标；s：当前路径和；t：当前路径。
    private void dfs(int u, int s, List<Integer> t) {
        if (s > target) {
            return;
        }

        if (s == target) {
            answer.add(new ArrayList<>(t));

            return;
        }

        for (int i = u; i < candidates.length; ++i) {
            // 同层遇到重复值只保留第一个；条件必须是 i > u 而不是 i > 0。
            if (i > u && candidates[i] == candidates[i - 1]) {
                continue;
            }

            t.add(candidates[i]);
            // 传 i + 1：每个下标最多使用一次。
            dfs(i + 1, s + candidates[i], t);
            t.remove(t.size() - 1);
        }
    }
}

import (
    "slices"
    "sort"
)

func combinationSum2(candidates []int, target int) [][]int {
    var answer [][]int
    var t []int
    // 排序让相同值相邻，是同层去重条件成立的前提。
    sort.Ints(candidates)

    // u：本层允许选取的最小下标；s：当前路径和；t：当前路径。
    var dfs func(u, s int, t []int)
    dfs = func(u, s int, t []int) {
        if s > target {
            return
        }
        if s == target {
            answer = append(answer, slices.Clone(t))
            return
        }
        for i := u; i < len(candidates); i++ {
            // 同层遇到重复值只保留第一个；条件必须是 i > u 而不是 i > 0。
            if i > u && candidates[i] == candidates[i-1] {
                continue
            }
            t = append(t, candidates[i])
            // 传 i+1：每个下标最多使用一次。
            dfs(i+1, s+candidates[i], t)
            t = t[:len(t)-1]
        }
    }

    dfs(0, 0, t)
    return answer
}

复杂度分析

  • 时间复杂度：$O(n2^n)$ 最坏上界。最多访问所有下标子集，每个状态的候选扫描和答案复制至多为 $O(n)$，排序的 $O(n\log n)$ 包含在该上界内；实际会被同层去重和目标和剪枝缩减。
  • 空间复杂度：不计结果为 $O(n)$，用于路径、递归栈及排序工作空间。正数约束还会限制实际路径深度。

关键点总结

[!green]

  • i + 1 解决位置不能复用，同层跳过相同值解决答案不能重复。
  • 同值后继分支的结果被前一个分支覆盖，不要求两棵搜索子树完全相同。
  • 相邻去重依赖排序，而不同层仍可以选取不同位置上的相同值。

易错点总结

[!yellow]

  • 同层去重条件必须是 i > u，写成 i > 0 会禁用下一层需要的同值元素。
  • 下一层传 i + 1；传 i 会重复使用当前位置。
  • 达到目标时先保存副本，再结束该分支，不能和超额情况一起直接丢弃。
  • 路径必须撤销末项，答案也必须复制，避免后续分支相互影响。

相似题目

题目 难度 关联与区别
39. 组合总和 中等 原题候选可重复取，本题一个下标最多取一次，递归起点需前进。
90. 子集 II 中等 同样对排序后的重复值做同层去重，本题再增加目标和条件。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/98156642
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！