39. 组合总和

题目链接（中等）

题目描述

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

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

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

数据范围：

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

示例

示例 1：

输入： candidates = [2,3,6,7], target = 7
输出： [[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7。注意 2 可以使用多次。7 也是一个候选，7 = 7。仅有这两种组合。

示例 2：

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

示例 3：

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

方法一：搜索回溯

思路及解法

对于这类寻找所有可行解的题，都可以尝试用「搜索回溯」的方法来解决。

定义递归函数 dfs(target, combine, idx)，表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine。

递归的终止条件为 target <= 0 或者 candidates 数组被全部用完。在当前的函数中，每次有两种选择：

1. 跳过当前数：执行 dfs(target, combine, idx + 1)；
2. 使用当前数：由于每个数字可以被无限制重复选取，搜索的下标仍为 idx，执行 dfs(target - candidates[idx], combine, idx)，然后把当前数加入 combine。

使用当前数前要判断 target - candidates[idx] >= 0，若为负数则不能选，相当于一种剪枝。

将整个搜索过程用一棵树表示：每次延伸出两个分叉，直到递归终止条件，就能不重复且不遗漏地找到所有可行解。

代码

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        def dfs(target: int, combine: list[int], idx: int) -> None:
            if idx == len(candidates):
                return
            if target == 0:
                ans.append(combine[:])
                return

            # 直接跳过当前数
            dfs(target, combine, idx + 1)

            # 选择当前数（可重复选取，所以 idx 不变）
            if target - candidates[idx] >= 0:
                combine.append(candidates[idx])
                dfs(target - candidates[idx], combine, idx)
                combine.pop()

        ans = []
        dfs(target, [], 0)
        return ans

复杂度分析

• 时间复杂度：$O(S)$，其中 $S$ 为所有可行解的长度之和。搜索树的叶子节点深度之和即为解的总长度。一个较松的上界是 $O(n \cdot 2^n)$，但实际远小于此，因为递归中会用 target - candidates[idx] >= 0 剪枝。
• 空间复杂度：$O(\text{target})$，除答案数组外，空间复杂度取决于递归栈深度，最差情况下需要递归 $O(\text{target})$ 层。