好的，我们接下来讲解 LeetCode 第 39 题「组合总和」。

1. 题目描述

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

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

题目数据保证，对于输入的目标数 target，所有可能的组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组 2+2+3=7
7 单独一组 7=7

示例 2：

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

注意：

• 解集不能包含重复的组合。

2. 题目理解与思路分析

关键点

1. 同一个数字可以无限次使用。
2. 数组元素无重复。
3. 组合不能重复，比如 [2,2,3] 和 [2,3,2] 是同一个组合，不应重复出现。

思路

这个问题是典型的 回溯法（DFS） 问题。
我们可以把问题看作是在一棵树中搜索所有可能的组合，树的每一层代表尝试不同的候选数字，但为了避免重复组合，需要按一定顺序选取数字（例如从小到大），并且每次从当前位置或之后的位置选取数字（不能回头选前面的数字，否则会出现 [2,3,2] 这样的重复）。

3. 回溯法设计

步骤

1. 对数组排序（不是必须，但能帮助剪枝）。
2. 使用 DFS 递归搜索：
   • 参数：当前组合 path，当前和 current_sum，开始搜索的索引 start。
   • 如果 current_sum == target，将 path 加入结果列表。
   • 如果 current_sum > target，直接返回（剪枝）。
   • 否则，从 start 到数组末尾遍历：
     • 将 candidates[i] 加入 path。
     • 递归调用，start 从 i 开始（因为可重复选取）。
     • 回溯：从 path 中移除刚才加入的数字。

为什么从 start 开始？

因为允许重复选取，所以递归时仍从 i 开始（而不是 i+1），这样下一次递归还可以选 candidates[i]。
同时，由于不会回头选 i 之前的数字，所以不会出现顺序不同的重复组合。

4. 举例说明

以 candidates = [2,3,6,7], target = 7 为例：

排序后仍是 [2,3,6,7]。

搜索树（简化）：

• 从 2 开始：
  • 选 2 → 剩余 5：
    • 再选 2 → 剩余 3：
      • 再选 2 → 剩余 1（剪枝）
      • 选 3 → 剩余 0 → 得到 [2,2,3]
    • 选 3 → 剩余 2（剪枝，因为 2<3 不能选 2 了？不对，这里索引是 1，还可以选 3，但剩余 2<3 剪枝）
    • 选 6 → 剩余 -1（剪枝）
  • 选 3 → 剩余 4：
    • 选 3 → 剩余 1（剪枝）
  • 选 6 → 剩余 1（剪枝）
  • 选 7 → 剩余 0 → 得到 [7]
• 从 3 开始（略，因为上面已经覆盖）

5. 代码实现（Python）

def combinationSum(candidates, target):
    def backtrack(start, path, current_sum):
        if current_sum == target:
            res.append(path[:])
            return
        if current_sum > target:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, current_sum + candidates[i])
            path.pop()
    
    res = []
    candidates.sort()  # 排序便于剪枝
    backtrack(0, [], 0)
    return res

6. 复杂度分析

• 时间复杂度：最坏情况是树的所有节点都被访问，组合数指数级，但题目保证组合数少于 150 个，所以实际可行。
• 空间复杂度：主要是递归栈的深度，最坏为 O(target / min(candidates))。

7. 总结

这道题是回溯算法的经典应用，关键点在于：

• 通过 start 参数避免重复组合。
• 允许重复选取，所以递归时 start 从 i 开始而不是 i+1。
• 排序后可以在递归时提前剪枝，提升效率。

这样，我们就能系统地找出所有可能的组合，并且不会重复。