组合总和

题目链接

题目原文 给定一个无重复元素的数组 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的基础上,每个组合需要进行重复选择的次数。
因为是大OO分析,所以取最坏情况。
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))

因此本题的时间复杂度为O(k22n)O(k^2*2^n),其中k=target,2n2^n是所有组合的个数。

参考

https://leetcode.com/problems/combination-sum/discuss/16634/If-asked-to-discuss-the-time-complexity-of-your-solution-what-would-you-say/16467