好的，我们接下来讲解 LeetCode 第 39 题：组合总和（Combination Sum）。

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 单独构成一组解。

示例 2：

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

示例 3：

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

2. 题目要点分析

• 无重复元素数组：数组中的数字都是唯一的。
• 数字可无限重复使用：比如示例1中，数字 2 可以被使用多次。
• 解集不能包含重复的组合：例如 [2, 2, 3] 和 [2, 3, 2] 是同一个组合，结果中只应出现一次。
• 组合问题：需要枚举所有可能的组合，并检查它们的和是否等于 target。
• 数据规模较小（组合数 < 150），可以使用回溯（DFS）方法。

3. 解题思路：回溯法（DFS）

这类组合问题，非常适合用 深度优先搜索（DFS） 来解决，也常称为 回溯法。

3.1 为什么用回溯？

• 我们需要枚举所有可能的组合，而组合的长度是不固定的。
• 回溯法可以系统地遍历所有可能性，并在满足条件时记录结果，不满足时及时剪枝。

3.2 核心思想

1. 从数组的第一个元素开始，尝试选择它 0 次、1 次、2 次……直到总和超过 target。
2. 每次选择后，递归处理剩下的目标值（target - 当前选择数字）。
3. 如果正好等于 0，说明找到一组解，加入结果集。
4. 如果小于 0，说明当前路径不可能得到解，回溯到上一步。
5. 为了避免重复组合（如 [2,2,3] 和 [2,3,2]），我们在递归时 只从当前索引或之后开始选择，不会回头选择前面的数字，这样自然保证了组合的唯一性（按非递减顺序）。

4. 回溯步骤详解

我们以 candidates = [2,3,6,7], target = 7 为例，模拟 DFS 过程。

4.1 定义 DFS 函数

def dfs(start, target, path):

• start：当前可选的起始索引（避免重复组合）。
• target：剩余需要凑的目标值。
• path：当前已选择的数字列表。

4.2 递归过程

1. 初始调用：dfs(0, 7, [])
2. 从索引 0（数字 2）开始：
   • 选 2：target = 5, path = [2] → 调用 dfs(0, 5, [2])
     • 再选 2：target = 3, path = [2,2] → 调用 dfs(0, 3, [2,2])
       • 再选 2：target = 1, path = [2,2,2] → 调用 dfs(0, 1, [2,2,2])
         • 再选 2：target = -1 < 0，返回（剪枝）
       • 选 3：target = 0，找到解 [2,2,3]，加入结果。
       • 选 6：target = -3 < 0，返回。
       • 选 7：target = -4 < 0，返回。
     • 选 3：target = 2，path = [2,3] → 调用 dfs(1, 2, [2,3])
       • 选 3：target = -1 < 0，返回。
       • 选 6、7 也会小于 0，返回。
     • 选 6、7 也会小于 0，返回。
   • 选 3：target = 4, path = [3] → 调用 dfs(1, 4, [3])
     • 选 3：target = 1 → 再选 3：target = -2，返回。
     • 选 6、7 也会小于 0，返回。
   • 选 6：target = 1 → 再选 6：target = -5，返回。
   • 选 7：target = 0，找到解 [7]，加入结果。

最终结果：[[2,2,3], [7]]。

5. 代码实现（Python）

def combinationSum(candidates, target):
    def dfs(start, target, path):
        if target == 0:
            res.append(path[:])  # 记录解
            return
        for i in range(start, len(candidates)):
            num = candidates[i]
            if target - num < 0:
                continue  # 剪枝
            path.append(num)
            dfs(i, target - num, path)  # 注意这里 start 是 i，不是 i+1，因为可重复选
            path.pop()  # 回溯，撤销选择

    res = []
    candidates.sort()  # 可选，便于剪枝
    dfs(0, target, [])
    return res

代码解释：

• dfs(i, target - num, path)：因为数字可重复使用，所以下一层递归仍然从 i 开始。
• path.pop()：回溯的关键步骤，撤销上一步的选择，以便尝试下一个选择。
• candidates.sort()：排序不是必须的，但可以提前剪枝（如果 target - num < 0，由于数组已排序，后面更大的数也会 < 0，可提前终止循环）。

6. 复杂度分析

• 时间复杂度：最坏情况是树形递归的所有节点数。由于每个数字可重复使用，树的最大深度是 target / min(candidates)，组合数少于 150，实际可行。
• 空间复杂度：主要取决于递归栈的深度，最坏情况是 O(target / min(candidates))。

7. 总结

• 组合总和 是经典的回溯问题，通过 DFS 枚举所有可能组合。
• 关键点在于 递归时传递起始索引 避免重复组合，以及 回溯时撤销选择。
• 可重复选数字，所以递归时 start 不变；若不可重复选（如组合总和 II），则 start 要 +1。

这样循序渐进地讲解，你是否对这道题的思路和实现有了清晰的理解？