给你一个 无重复元素 的整数数组
candidates 和一个目标整数 target 。找出
candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target 的不同组合数少于 150 个。示例 1：
示例 2：
示例 3：
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates的所有元素 互不相同
1 <= target <= 40
解法一：回溯 DFS （推荐）
对于示例 1 ，
[2, 2, 3] 是一个合法组合，[2, 3, 2] 并不是另一个组合，它们只是顺序不同，本质上是同一个组合。题目要的是 combination，不是 permutation。所以这道题的关键是如何让每一种组合只被生成一次。我们要做的是枚举 “在保持非降序选择的前提下，下一步可以拿哪个数字”。
为了解决这个问题，我们用回溯构造组合，并且给
candidates 一个固定顺序，在搜索过程中只允许继续选择当前位置及其右侧的数字。 这样组合里的数字天然是按候选数组顺序构造出来的，不会出现 [2, 3, 2] 这种回头选择前面数字的情况。定义：
backtrack(start, remain) ，其中：start表示当前还能从哪个位置开始选，
remain表示还需要凑出的目标和。
也就是，当前还需要凑出
remain，并且接下来只能从 candidates[start:] 里选择数字。每次从
start 开始枚举候选数，选择 candidates[i] 后递归调用 backtrack(i, remain - candidates[i])。这里传 i 而不是 i + 1，是因为同一个数字可以重复使用；但不允许传回更小的下标，所以不会产生重复排列。当
remain == 0 时，说明当前路径是一个合法组合，把 path.copy() 加入答案；当当前数字超过
remain 时，由于数组已经排序，可以直接停止这一层搜索。示例1：
candidates = [2, 3, 6, 7], target = 7搜索从空组合
[] 开始。我们先允许选择 2，于是可以继续走到 [2]、[2, 2]、[2, 2, 2]，再往下加 2 会超过 7，所以回溯；接着在
[2] 后面尝试 3，得到 [2, 3] , 在 [2, 2] 后面尝试 3，得到 [2, 2, 3]，正好等于 7。而
[2, 3] 的下一层搜索中 remain = 2 < 3，直接停止这一层搜索。也不会再回头选择
2，所以不会生成 [2, 3, 2]。最终合法答案是：
[[2, 2, 3], [7]]复杂度分析
设
N 是候选数个数，T 是 target，M 是候选数中的最小值。- 时间复杂度是：
O(N^(T/M + 1))
递归树的最大深度大约是
T / M，因为每次至少会加入一个值为 M 的数字。每层最多有 N 个分支。所以宽松上界是 O(N^(T/M + 1))。实际运行通常会小很多，因为一旦 remain < 0 或当前数字超过 remain，搜索会被剪枝。- 空间复杂度是：
O(T / M)
主要来自递归调用栈和当前路径
path。这里不把最终答案占用的空间计入辅助空间，因为输出本身可能很大。
解法二：二叉决策树回溯
把每个候选数看成一个决策点，对于每个
candidates[i]，我们有两个选择：- 选择它：把
candidates[i]加入当前组合。因为数字可以重复使用，所以递归时i不变；
- 跳过它：以后都不再使用
candidates[i]，所以递归到i + 1。
这个搜索树的设计非常重要。它不是随意枚举所有排列，而是把解空间切成两块：
- 左分支：至少包含一个当前数字；
- 右分支：完全不包含当前数字。
这两个分支天然互斥，所以不会生成重复组合。
比如对于数字
2：- 选择分支会覆盖所有包含至少一个
2的组合；
- 跳过分支会覆盖所有不包含
2的组合。
这就像在递归地回答一个问题：
当前这个数字，我还要不要继续用？
如果要继续用，就留在同一个下标；如果不用了，就彻底进入下一个候选数。
复杂度分析
- 时间复杂度是：
O(2^T)
这个写法的搜索树每一层有两个分支：“选当前数字”或“跳过当前数字”。
由于候选数都是正数，递归深度最多和
target 成正比。它是指数级搜索，依赖剪枝和目标值大小。
- 空间复杂度是：
O(T / M)
主要来自递归栈和当前组合。最终答案占用空间不计入辅助空间。
总结
这两种写法本质上都在 构造一棵不会产生重复组合的搜索树。
区别在于搜索树的形状不同。
第一种 for-loop 写法，每一层直接枚举“下一个选哪个候选数”。
第二种二叉决策树写法，每一层只围绕当前候选数做两个选择：“继续使用它”或者“彻底跳过它”。
可以这样理解：
最终它们都依赖同一个核心约束：
搜索只能往候选数组的右侧推进，不能回头选择前面的数字。
正是这个约束消除了
[2, 2, 3]、[2, 3, 2]、[3, 2, 2] 之间的重复排列。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-39-组合和
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 34] 在排序数组中查找元素的第一个和最后一个位置
下一篇
[Leetcode 42] 接雨水