组合总和
题目原文
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题目解析
本题的解空间巨大，因为可以重复选择元素，当候选集和target很大时，解空间树将很深。因此，我们需要优化剪枝条件，降低时间复杂度。
解题方法
剪枝条件
首先，从一个例子出发，分析获得结果数组的流程，当候选集为[2,3,6,7],target为6时，DFS搜索过程及可剪枝情况如下：
流程图我们可以归纳出一下几个剪枝条件:
- 当前选择的所有数总和大于target；
- 候选集中的数大于target；
- 已选择n个数，在递归下一层时，这个n个数的和加上候选集中最小值也比target大，舍弃这一层（如图中，黄色框部分）；
- 重复选择，当给定候选集是排序后的情况下，每次选择只选择比当前选择大于等于的数即可避免重复（如图中方框标注的情况）。
解题代码
复习一下DFS回溯的框架，使我们解题时条理更加清晰。
#记录选择 path=[] def dfs(node): if 终止条件: #保存结果 return #剪枝 for 某节点 in 当前可选择节点: #剪枝 #进行选择 path.append(node) dfs(node) #取消选择，回溯 path.pop()
代码如下，可直接复制到leetcode运行：
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: #边界情况，直接返回 if len(candidates)==0: return [[]] #记录结果 result=[] path=[] count=0 candidates.sort() def dfs(cur_num): # 声明全局变量 nonlocal count # 终止条件 if count==target: # 添加到结果 result.append(list(path)) return elif count>target: # 当前总和大于target，剪枝 return elif count + min(candidates) > target: # 当前总和加上候选集中最小的数，仍大于target，剪枝 return for num in candidates: if num > target: # 候选集中的数大于target continue if num < cur_num: # 避免重复 continue # 进行选择 path.append(num) count+=num dfs(num) # 取消选择，回溯 path.pop() count-=num dfs(0) return result
复杂度分析
会发现，针对这种可重复的组合问题，它的复杂度很难分析，可以说十分抽象。那么对于这种时间复杂度如何分析呢？
我们可以从最简单的情况考虑，给定list[1,2,3]和target 1000。
问题1：选择多少次1能得到1000？
当然是1000次
问题2：list[1,2,3]共有多少种组合?
[[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
C(3,1) + C(3,2) + C(3,3)
问题3：在问题2的基础上，每个组合需要进行重复选择的次数。
因为是大分析，所以取最坏情况。
C(3,1) * target/1 + C(3,2) * target/2 + C(3,3) * target(3)
问题4：在问题3的基础上，加上target
target * (C(3,1) * target/1 + C(3,2) * target/2 + C(3,3) * target(3))
因此本题的时间复杂度为，其中k=target，是所有组合的个数。
