39. 组合总和 (Medium)

专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/combination-sum/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

示例 2：

输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入：candidates = [2], target = 1
输出：[]

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素互不相同
• 1 <= target <= 40

---

题目详细分析

数据范围含义：

• target <= 40 且 candidates[i] >= 2：递归深度最多 20 层（全选最小元素 2），剪枝空间大。
• candidates.length <= 30 但实际搜索中因为有剪枝，不会遍历所有分支。
• 元素互不相同：不需要处理同值去重。

关键特性——可重复选取：

• 与标准子集/组合问题的核心区别：每个元素可以被选中无限次。递归时传 i 而不是 i+1 即可实现。
• 但组合本身不关心顺序，所以仍需用 start 参数避免 [2,2,3] 和 [2,3,2] 这样的重复。

剪枝条件：

• 排序后，当 candidates[i] > remaining 时可以 break（因为后面的元素更大），显著减少搜索空间。

---

小白版直白理解

就像你去超市买东西，预算 7 元，货架上有标价 2 元、3 元、6 元、7 元的商品（每样商品无限供应）。你要找出所有正好花光 7 元钱的购买方案。你可以买 3 个 2 元商品 + 1 个 1 元商品…哦不对没有 1 元的。你可以买 2 个 2 元 + 1 个 3 元（2+2+3=7），或者直接买 1 个 7 元商品。

每样商品买多少个都可以，但不能赊账（总和必须恰好等于 target），也不能超出预算（超出就停止挑选）。

---

解题思路

思路一：回溯 + 排序剪枝（推荐）

核心思想： 先排序，然后用回溯法逐个选取元素。每次可以从当前及之后的元素中选择（可重复选当前），当累计和超过 target 时剪枝。

决策树可视化（以 candidates=[2,3,6,7], target=7 为例）：

                    []
         /          |          \        \
       [2]         [3]        [6]      [7]
      /   \         |          |
   [2,2] [2,3]   [3,3]     [6]→超了
    /      |        |
 [2,2,2]  [2,3]  [3,3]→超了
   |        |
 超了   [2,2,3]=7 ✓

def combinationSum(candidates, target):
    res = []
    candidates.sort()  # 排序是剪枝的前提
 
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path[:])  # 找到一个合法组合
            return
 
        for i in range(start, len(candidates)):
            # 剪枝：因为已排序，当前元素过大则后续更大，直接跳出
            if candidates[i] > remaining:
                break
 
            path.append(candidates[i])
            # 传 i 而不是 i+1：允许重复选取当前元素
            backtrack(i, path, remaining - candidates[i])
            path.pop()
 
    backtrack(0, [], target)
    return res

思路二：不排序的回溯（无剪枝版本）

核心思想： 如果面试时要求不能修改原数组，或者需要展示基础回溯思想，可以不排序，跳过剪枝即可。

def combinationSum(candidates, target):
    res = []
 
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        if remaining < 0:
            return  # 超过目标，回溯
 
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])
            path.pop()
 
    backtrack(0, [], target)
    return res

时间复杂度： O(2^n) 最坏（无剪枝时），有剪枝后实际远小于此。 空间复杂度： O(target/min(candidates))，递归深度由 target 和最小元素决定。

---

易错点

1. start 参数传 i 还是 i+1：本题允许重复选取同一元素，所以递归传 i（还能选自己）；如果不允许重复则传 i+1（如 40-组合总和 II）。
2. 剪枝条件用 break 还是 continue：排序后用 break，因为后面的元素更大，一定都会超；不排序则只能用 continue。
3. remaining 的计算：remaining - candidates[i] 作为参数传入，不要在函数体内修改外部变量。
4. 没有排序就跳出的风险：如果不排序就使用 break 剪枝，会遗漏正确结果。例如 [3,2,5]，target=5，遇到 3<5 就 break 会跳过 [5]。
5. 结果去重：必须使用 start 参数，否则会出现 [2,2,3] 和 [2,3,2] 这样的重复组合。

---

框架提炼

组合总和回溯模板：

def backtrack(start, path, remaining):
    if remaining == 0:
        res.append(path[:])
        return
 
    for i in range(start, len(candidates)):
        # 可选剪枝：排序后使用
        if candidates[i] > remaining:
            break
 
        path.append(candidates[i])
        backtrack(i, path, remaining - candidates[i])  # 传 i 可重复选
        path.pop()

“可重复选取”与”不可重复选取”对比：

特性	可重复（39题）	不可重复（40题/78题）
递归参数	backtrack(i, ...)	backtrack(i+1, ...)
剪枝方式	排序后 if candidates[i] > remaining: break	同左
去重要求	只需 start 控制	排序 + 相邻去重

三种组合问题的递进关系：

1. 78-子集：枚举所有组合，无目标和约束，每个元素只能用一次，每个节点都记录。
2. 39-组合总和：有目标和约束（剪枝依据），元素可重复使用。
3. 40-组合总和 II：有目标和约束，不可重复使用，且有重复元素需去重。

---

关联题目

• 78-子集 — 最基础的组合枚举，与本题的 start 控制逻辑一致，区别在于无目标和约束。
• 46-全排列 — 排列 vs 组合：排列用 visited 控制，组合用 start 控制。
• 40-组合总和II — 本题的进阶版：不能重复选同一元素，且 candidates 可能有重复。
• 216-组合总和III — 固定组合大小（k 个数），再加目标和约束，综合了组合总和与 77-组合的元素。