组合总和
题目原文
给定一个无重复元素的数组 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,是所有组合的个数。