LeetCode LCR 081. 组合总和

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

题目描述

✅ LCR 081. 组合总和

image-20260929005918833

image-20260929005918834

题意分析

从互不相同的正整数候选中选数，使总和恰好为 target，返回全部不同组合。每个候选可以重复使用，但改变选取顺序不产生新组合。

本题候选值范围为 1..200，目标范围为 1..500，不能假设候选至少为 2 或搜索最多只有 20 层。所有候选为正数，才保证重复选取时路径和严格增加，超额分支能够终止。

解法：固定最小候选下标的回溯

核心思路

[!blue]

相同组合只在各个数字的选取次数上有区别，可以统一按候选下标非递减的顺序生成。设 u 为本层允许选取的最小下标，本层只枚举 i >= u，选完后下一层仍从 i 开始：保留当前下标允许重复选取，禁止回到更小下标则避免同一组合换序重复。

t 保存当前路径，s 是路径中所有数的和。s == target 时保存路径副本并返回；s > target 时也返回，因为继续加入正数只会更大。这两个条件同时保证了正确收集和搜索终止。

每次追加候选后递归，再删除末项恢复路径。数组本身没有排序，所以当前候选使路径超额，只能结束这个分支，不能据此断定后面的候选也都过大。

解题步骤

  1. 初始化结果，从 s = 0、u = 0 和空路径开始搜索。
  2. 总和达到目标时复制路径加入结果；总和超过目标时直接返回。
  3. 枚举从 u 到末尾的候选下标 i，将该值加入路径。
  4. 递归处理新的总和，并把最小候选下标设为 i。
  5. 返回后删除路径末项，继续尝试其他候选。所有分支都未命中时返回空结果。

代码实现

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        answer = new ArrayList<>();
        this.target = target;
        this.candidates = candidates;
        dfs(0, 0, new ArrayList<>());

        return answer;
    }

    // s：当前路径和；u：本层允许选取的最小下标；t：当前路径。
    private void dfs(int s, int u, List<Integer> t) {
        if (s == target) {
            // t 全程复用，必须深拷贝一份再存入结果。
            answer.add(new ArrayList<>(t));

            return;
        }

        if (s > target) {
            // 元素全为正，继续向下只会更大，直接剪枝。
            return;
        }

        for (int i = u; i < candidates.length; ++i) {
            int c = candidates[i];

            t.add(c);
            // 传 i 而非 i + 1：同一元素允许重复选取；传 i 而非 0：禁止回头，实现组合去重。
            dfs(s + c, i, t);
            t.remove(t.size() - 1);
        }
    }
}

func combinationSum(candidates []int, target int) [][]int {
    var answer [][]int

    // s：当前路径和；u：本层允许选取的最小下标；t：当前路径。
    var dfs func(s, u int, t []int)
    dfs = func(s, u int, t []int) {
        if s == target {
            // t 底层数组会被后续 append 覆写，必须拷贝一份再存入结果。
            answer = append(answer, append([]int(nil), t...))
            return
        }
        if s > target {
            // 元素全为正，继续向下只会更大，直接剪枝。
            return
        }
        for i := u; i < len(candidates); i++ {
            c := candidates[i]
            t = append(t, c)
            // 传 i 而非 i+1：同一元素允许重复选取；传 i 而非 0：禁止回头，实现组合去重。
            dfs(s+c, i, t)
            t = t[:len(t)-1]
        }
    }

    var t []int
    dfs(0, 0, t)
    return answer
}

复杂度分析

设实际访问的搜索状态数为 V，全部输出组合的元素总数为 R，令 $d=\lfloor target/\min(candidates)\rfloor$。

  • 时间复杂度：$O(V+R)$，包含未命中的分支和保存答案的复制开销；最坏搜索仍为指数级，不能只按答案条数计时。
  • 空间复杂度：不计结果为 $O(d+1)$，用于路径和递归栈，超额时还可能多进入一层；输出占 $O(R)$。

关键点总结

[!green]

  • 候选值互异，按下标非递减生成就能唯一表示每种选取次数，不需要额外集合去重。
  • 下一层传 i 允许复用；传 i + 1 会变成每个位置最多使用一次。
  • 正数保证超额后不可能回到目标，也是递归深度有限的依据。

易错点总结

[!yellow]

  • 下一层不能回到下标 0，否则会把同一组合的不同顺序重复输出。
  • 当前实现未排序，不能因一个候选超额就 break 整层循环。
  • 保存路径副本，并在返回后撤销末项，避免答案或后续分支被覆盖。
  • 不要沿用主站其他版本的数值范围来估计本题递归深度。

相似题目

题目 难度 关联与区别
40. 组合总和 II 中等 同样搜索目标和组合，原题每个输入位置只能用一次且可能有重复，本题允许同一候选反复选择。
377. 组合总和 Ⅳ 中等 同样由候选组成目标和，原题把不同排列顺序视为不同方案，本题不区分顺序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/55988125
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！