组合总和

🟡 Medium · 🏷️ 数组、回溯 · LeetCode#39

📖 题目

给一组不含重复数字的候选数和目标值 target，找出所有和为 target 的组合，同一个数可以重复选。

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

💡 思路

组合的变体：终止条件从"凑满 k 个数"变成"凑到 target"，而且同一个数可以重复选——这意味着递归时要传 i（可以选自己），而不是 i+1（跳过自己）。但 start 仍然保留，防止往回选，否则 [2,2,3] 和 [3,2,2] 会被算成两个不同结果。

剪枝：一旦当前路径的和加上下一个候选数就超过了 target，这条分支直接放弃，不用往下递归。

💻 代码

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        n = len(candidates)

        def backtrack(start: int, path: List[int], total: int):
            if total == target:
                result.append(path[:])
                return
            for i in range(start, n):
                c = candidates[i]
                if total + c <= target:            # 剪枝
                    path.append(c)
                    backtrack(i, path, total + c)   # 传 i，不是 i+1：可以选自己
                    path.pop()

        backtrack(0, [], 0)
        return result

时间复杂度最坏 O(n^(target/min))，min 是最小的候选数；空间复杂度 O(target/min)，递归深度。

🔀 递归传参速查

三种"能不能选自己/能不能回头"的组合，对应三种传参方式：

传参	含义	用在哪
i（选自己）	能重复选，不能回头	这题
i + 1（跳过自己）	每个只能用一次，不能回头	组合、子集
不传（从头扫）	能回头，靠 not in path 去重	排列

跟零钱兑换问题结构其实一样（从一组数里可重复选凑出目标值），区别是那题用 DP 求"最少要几枚"，这题用回溯找"所有可能的组合"——求最优值用 DP，求所有方案用回溯。