Combination Sum
你会得到一个由不同正整数组成的列表 candidates，以及一个正整数 target。找出所有总和恰好等于 target 的候选数组合，每个候选数都可以使用任意次。[2, 3, 3] 和 [3, 2, 3] 是同一种组合。
将每种组合按升序排列，并按字典序排列这些组合：在两个组合首次出现不同的位置，值较小的组合排在前面。
函数
- candidatesinteger-array
- 你可以使用的不同值，顺序不限，每个值都可以使用任意多次
- targetinteger
- 每种组合的总和都必须恰好达到
- 返回值integer-2d-array
- 所有和为目标值的组合，每个组合中的数字按升序排列，组合按字典序排列
约束条件
1 ≤ candidates.length ≤ 502 ≤ candidates[i] ≤ 5002 ≤ target ≤ 500- 所有
candidates中的值都不相同，且没有特定顺序。 - 至少有一种组合可以达到
target，且这样的组合最多有 150 种。
示例
- 输入
- candidates = [6, 2, 3]target = 8
- 输出
- [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
- 解释
- 按第二个值排序，4 个 2、2 + 3 + 3 和 2 + 6 都能得到 8。不使用 2 时，只剩下 3 和 6，它们的和都是 3 的倍数，而 8 不是。
- 输入
- candidates = [5, 3, 4]target = 11
- 输出
- [[3, 3, 5], [3, 4, 4]]
- 解释
- 3 + 3 + 5 和 3 + 4 + 4 都等于 11，并且
[3, 3, 5]排在前面，因为它的第二个值 3 比 4 小。只用 4 和 5 无法凑出 11。
- 输入
- candidates = [4, 9]target = 9
- 输出
- [[9]]
- 解释
- 单独的 9 是唯一答案：4 的倍数是 4、8 和 12，而 4 + 9 已经是 13。
进阶
现在每个候选项最多只能使用一次，而且 candidates 中可能包含重复的值。你要如何修改搜索，才能避免同一种组合出现两次？
提示
逐个打开提示，每个都会多透露一点。
[2, 3, 3]和[3, 2, 3]是同一种组合。如果你只按值的升序构建组合，每种组合可以用多少种方式构建？对候选数排序，每次添加一个值，逐步构建组合。添加
nums[i]后，下一个值可以再次是nums[i]，也可以是后面的任意值，但不能是前面的值。编写
backtrack(start, remaining)。当remaining为 0 时，保存当前值的副本。否则，从start开始循环：添加一个值，使用相同的索引和更小的剩余值进行递归，然后移除该值。当遇到第一个大于remaining的值时，退出循环。
题解
陷阱在于重复构建相同的组合：2, 3, 3 和 3, 2, 3 是同一个答案。按升序构建每个组合，这样每个组合就只有一条路径；同时对候选数排序，这样一旦下一个值大于剩余值，就可以立即停止该分支。
尝试每个候选项的所有数量
结果正确，但无法在最大的测试中运行完毕
思路
每种候选数用了多少个，就能完整描述一种组合：[2, 3, 3] 表示一个 2、两个 3，没有 6。对于每个已排序的候选数，尝试从 target / c 到 0 的每种数量，只保留总和恰好等于 target 的选择。每种组合都对应唯一的一组数量，因此不会重复找到。优先尝试较大的数量会得到字典序：如果两个答案第一次出现不同，那么数量较多的那个答案仍包含该值，而另一个答案包含更大的值。
对于 [2, 3, 6] 和目标值 8，生成 3 个答案需要遍历 5 × 3 × 2 = 30 个叶节点。每个大于 target / 2 的候选数都会使叶节点数量翻倍，因此有 40 个这样的候选数时，叶节点数量为 2^40，约为 10^12。
算法
- 对候选数排序，并为每个值保留一个计数。
- 在
choose(i, total)中，让k从target / nums[i]递减到 0，尝试每个计数，并调用choose(i + 1, total + k × nums[i])。 - 为每个值确定计数后，如果
total等于target，就保留这个组合，并根据各计数将其写出。 - 调用
choose(0, 0)。
def combinationSum(candidates, target):
nums = sorted(candidates)
counts = [0] * len(nums)
result = []
def choose(i, total):
if i == len(nums):
if total == target:
combo = []
for value, k in zip(nums, counts):
combo.extend([value] * k)
result.append(combo)
return
# Most copies first, so the combinations come out in lexicographic order.
for k in range(target // nums[i], -1, -1):
counts[i] = k
choose(i + 1, total + k * nums[i])
counts[i] = 0
choose(0, 0)
return result按升序回溯并剪枝
思路
放入 nums[i] 后，下一个值可以再次是 nums[i]，也可以是后面的任意值，但不能是前面的值。每个组合都只有一种升序排列，因此也只有一条路径，并且永远不会构造出 [3, 2, 3]。
对于排序后的 [2, 3, 6] 和目标值 8，路径 2, 2, 2, 2、2, 3, 3 和 2, 6 都能得到 8。路径 2, 2, 3 会剩下 1，于是停止，不会查看 6；路径 3, 3 会剩下 2，而没有哪个值能凑出 2。这样只需调用 12 次，而计数法要处理 30 个叶节点。
在每一层，循环都会先尝试较小的值，因此答案会按字典序排列。没有一个答案是另一个答案的前缀，因为这些值都是正数，而且每个答案的总和都相同。
算法
- 对候选值排序。
- 在
backtrack(start, remaining)中，当remaining为 0 时，保存共享path的副本。 - 否则，让
i从start开始循环。如果nums[i] > remaining，就跳出循环：后面的值都更大。 - 添加
nums[i]，调用backtrack(i, remaining - nums[i])，然后将它移除。 - 调用
backtrack(0, target)，并返回保存的组合。
def combinationSum(candidates, target):
nums = sorted(candidates)
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(nums)):
if nums[i] > remaining:
break # sorted, so every later value is too big as well
path.append(nums[i])
backtrack(i, remaining - nums[i]) # i, not i + 1: nums[i] may repeat
path.pop()
backtrack(0, target)
return result
易错点和边界情况
- 在每一层都遍历所有候选项，而不是从当前索引开始。这样，
[2, 3, 3]、[3, 2, 3]和[3, 3, 2]会变成 3 个答案。 - 递归时使用
i + 1而不是i。这样每个值最多只能出现一次，因此会漏掉[2, 2, 2, 2]。 - 保存
path本身，而不是它的副本。这样每个已保存的答案都会指向同一个列表，而回溯会在最后将列表清空。 - 对没有排序的候选项使用
break。对于[6, 2, 3]，当还差 2 时，循环会在遇到 6 时停止，永远不会尝试 2。
常见问题3
组合总和的时间复杂度是多少？
回溯搜索的复杂度是指数级的。给定 n 个候选值、目标值 t 和最小候选值 m，一个组合最多包含 t/m 个值，每个值最多有 n 种选择：O(n^(t/m))。额外空间为路径和调用栈所需的 O(t/m)，以及输出所需的空间。
在 Combination Sum 中，为什么递归时传入的是 i，而不是 i + 1？
使用 i 进行递归，可以让下一个值再次选择同一个候选值，这样一个值就能被使用多次。使用 i + 1 进行递归会跳过它，因此每个候选值最多只能使用一次。
组合总和问题可以用动态规划解决吗？
是的。对于从 0 到 target 的每个总和，都保留能达到该总和的组合，每次添加一个候选值，这样每个列表都会保持升序。它不会重复探索死胡同，但会为每个总和存储所有部分组合，这会消耗多得多的内存。由于输出本身可能呈指数级增长，通常会使用回溯法。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def combinationSum(candidates, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
candidates = [6, 2, 3] target = 8
预期输出
[[2, 2, 2, 2], [2, 3, 3], [2, 6]]