39. 组合总和 - Combination Sum

🎯 问题描述（来源于LeetCode）

描述：
给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复选取。
解集不能包含重复的组合（顺序不同的相同组合视为同一组合）。

说明：

所有数字（包括 target）都是正整数。
每个组合中的数字可以按任意顺序排列，但解集中不能有重复组合。

示例：

示例 1：

1
2
3

输入: candidates = [2,3,6,7], target = 7
输出: [[2,2,3],[7]]
解释: 2+2+3=7，7=7。

示例 2：

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

💻 解题思路

思路：回溯法（DFS）允许重复选取

算法步骤

获取数组长度 n，初始化结果列表 ans 和当前路径列表 path。
定义递归函数 dfs(i, leave)，表示当前考虑下标 i 及之后的元素，剩余需要凑的目标值为 leave：
- 如果 leave == 0：找到一组解，将 path 的副本加入 ans，返回。
- 如果 i == n 或 leave < 0：超出范围或无法凑出，返回。
- 否则，进行两个分支：
  - 不选 candidates[i]：递归 dfs(i+1, leave)。
  - 选 candidates[i]：将 candidates[i] 加入 path，递归 dfs(i, leave - candidates[i])（注意 i 不变，允许重复选取），然后回溯弹出。
从 dfs(0, target) 开始搜索。
返回 ans。

代码实现

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        ans = []
        path = []
        
        def dfs(i, leave):
            if leave == 0:
                ans.append(path[:])
                return
            if i == n or leave < 0:
                return
            
            # 不选当前元素
            dfs(i+1, leave)
            # 选当前元素（允许重复）
            path.append(candidates[i])
            dfs(i, leave - candidates[i])
            path.pop()
        
        dfs(0, target)
        return ans

📊 性能分析

时间复杂度： $O(2^{target/min(candidates)})$ ，最坏情况下指数级。
空间复杂度： $O(target/min(candidates))$ ，递归栈深度最大为 target / min(candidates)。

思考

该解法采用经典的回溯框架，通过递归分支“选”与“不选”来枚举所有组合，并在“选”分支中保持当前下标 i 不变，实现元素的重复使用。代码结构清晰，剪枝条件 leave < 0 能提前终止无效分支。
优点：逻辑简单，直接符合题目要求；通过 path[:] 复制列表避免后续修改影响结果。
缺点：未对 candidates 排序，可能导致组合产生顺序不同的重复（但题目要求解集不重复，此代码通过递归顺序（不选再选）保证每个组合按原数组顺序递增，因此不会产生重复组合）。若希望进一步剪枝，可先对 candidates 排序，并在循环中跳过相同元素（但本题无重复元素）。
注意：递归分支顺序（先不选后选）确保了组合中元素呈非递减顺序（因为选当前元素后，后续只能选自身或更大下标，而不会选更小下标），从而避免重复。