LeetCode 39. 组合总和

约 4 分钟
文章信息 24 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 历史考题 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 亚马逊 携程 小红书 LeetCode 热题 100 面试经典 150 题
标签
数组 回溯 回溯经典题 组合问题
目录

题目描述

✅ 39. 组合总和

image-20250419031842243

image-20250419031857326

题意分析

输入一个「元素互不相同」的正整数数组 candidates 和目标值 target，要求找出所有和恰好等于 target 的组合。规则有两条：同一个数字可以被无限次选取，但答案中不能出现重复组合。

「组合」意味着不关心顺序：[2,2,3] 和 [2,3,2] 是同一个答案，只能输出一次。这是本题与排列类题目的根本区别，也是难点所在——枚举时必须有一套规则保证每个组合只被生成一次。

约束是很强的信号：数组长度不超过 30，候选数最小为 2，target 不超过 40，题目还保证答案组合数有限。这说明解空间不大，允许把所有可能性完整枚举一遍；组合长度也有天然上界，最多 $target / 2$ 个数。

边界上要注意：所有候选数都大于 target 时答案为空；target 恰好等于某个候选数时，单元素组合也是合法答案。

解法：排序后回溯枚举组合

核心思路

先排序候选数组，再用 start 限制下一层只能选择当前下标及其后面的数字，使每个组合按非降序生成，从源头避免重复。选择 candidates[i] 后仍从 i 开始递归，允许同一个数字重复使用；候选值大于剩余目标时直接停止枚举。

解题步骤

  • 将 candidates 升序排序，便于剪枝。
  • 回溯参数记录起始下标 start 和剩余目标 remain。
  • remain == 0 时复制当前路径并加入结果。
  • 从 start 开始枚举；若候选值大于 remain，结束本层循环。
  • 选择后递归传 i，返回时撤销选择。

代码实现

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

    private 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 (candidates[i] > remain) {
                break;
            }

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

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

    var backtrack func(int, int)
    backtrack = func(start, remain int) {
        if remain == 0 {
            result = append(result, append([]int(nil), path...))
            return
        }

        for i := start; i < len(candidates); i++ {
            if candidates[i] > remain {
                break
            }

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

    backtrack(0, target)
    return result
}

复杂度分析

  • 时间复杂度：$O(n \log n + S + Rd)$，S 为搜索树节点数，R 为答案数，d 为组合最大长度；最坏为指数级。
  • 空间复杂度：$O(d + \log n)$，不计返回结果；分别来自递归路径和排序栈。

关键点总结

  • start 保证组合按固定顺序生成，避免排列重复。
  • 递归传 i 表示当前数字可以继续使用。
  • 排序后才能在候选值过大时用 break 剪枝。
  • 保存答案时必须复制当前路径。

易错点总结

  • 递归传 i + 1 会让每个数字只能使用一次。
  • 每层都从下标 0 开始会生成重复组合。
  • 忘记撤销选择会污染后续分支。
  • 直接保存 path 引用，后续回溯会改坏已经记录的答案。

相似题目

题目 难度 考察点
40. 组合总和 II 中等 候选含重复且每个数只能用一次，需同层去重
77. 组合 中等 固定长度 k 的组合枚举，不涉及目标和
216. 组合总和 III 中等 限定 1–9 各用一次且限定个数，双重约束剪枝
377. 组合总和 Ⅳ 中等 顺序不同视为不同结果，转为计数型动态规划
LCR 080. 组合 中等 77 题镜像，组合模板的对照练习
LCR 081. 组合总和 中等 本题镜像，可复用同一份代码
LCR 082. 组合总和 II 中等 40 题镜像，重复元素去重的对照练习