39. 组合总和

题目链接：39. 组合总和

题目描述

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

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

核心思考：完全背包思想的回溯实现

由于题目允许“同一个数字可以无限制重复选取”，这本质上是一个完全背包类型的组合问题。我们依然通过深度优先搜索（DFS）进行回溯。

1. 递归状态：dfs(i, t) 代表我们当前正在考虑第 i 个候选数字，且剩余的目标数额为 t。
2. 两条决策分支：
   • 不选取当前数字：跳过当前元素，尝试下一个元素 dfs(i + 1, t)。
   • 选取当前数字：将 candidates[i] 加入路径。关键点在于，由于可以重复使用，递归时不需要将索引 i 加 1，而是继续停留在 i：dfs(i, t - candidates[i])。
3. 剪枝与终止：
   • 如果 t == 0：说明组合恰好满足目标，存入副本。
   • 如果 t < 0 或 i 越界：说明当前组合已作废，直接折返。

通过这种方式，我们可以在保证元素不重复引用的前提下，利用同一个索引的多次下潜来完成“无限复用”的逻辑搜索。

解题思路 (Python)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        ans = []

        def dfs(i, t):
            # 找到目标组合
            if t == 0:
                ans.append(path[:])
                return
            
            # 边界检查与剪枝
            if i == len(candidates) or t < 0:
                return

            # 分支 1：完全不考虑当前数字，跳到下一个
            dfs(i + 1, t)

            # 分支 2：考虑当前数字，并在之后继续允许从当前数字开始考虑
            path.append(candidates[i])
            dfs(i, t - candidates[i])
            # 回溯
            path.pop()

        dfs(0, target)
        return ans

复杂度分析

• 时间复杂度：指数级 $O(S)$，其中 $S$ 是所有可行解的长度之和。受限于搜索空间的深度和分支因子，虽然剪枝能够优化，但理论上限仍由目标值和最小候选项决定。
• 空间复杂度：$O(T/M)$，其中 $T$ 是目标值，$M$ 是候选项中的最小值。递归深度最坏情况下为 $T/M$ 层。