组合总和

39. 组合总和

问题描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同的组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

输入：candidates = [2,3,6,7]，target = 7

输出：[[2,2,3]，[7]]

解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

分析问题

这道题我们可以采用回溯算法来求解，即列出所有可能的组合，然后在这些组合中筛选出满足条件的序列。

还记得回溯算法的模板吗？如下所示。

result=[]
def backtrack(路径, 选择列表):
    if 满⾜结束条件:
        result.append(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择 

其中

• 路径：指从 candidates 选择出的元素。
• 选择列表：指给定的候选集合 candidates 。
• 结束条件：指路径列表中元素和是否等于目标值target，为了方便处理，我们可以定义一个变量 sum 表示路径中的元素和。

这里需要注意一点，对于求解组合相关的问题，我们需要一个变量start来表示 for 循序的起始位置，即从选择列表的哪个位置开始遍历。

代码如下所示。

class Solution:
    def combinationSum(self, candidates, target):
        result = []
        def backtrack(start, sum, path,candidates):
            #如果路径和大于target，直接返回
            if sum>target:
                return
            #如果路径和等于target,将该路径加入到结果列表中
            if sum==target:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):

                #添加元素到path（做选择）
                path.append(candidates[i])
                #递归查找
                backtrack(i, sum + candidates[i], path, candidates)
                #移除添加的元素（撤销选择）
                path.pop()

        backtrack(0,0,[],candidates)

        return result

通过剪枝进行优化处理

通过分析上述给出的代码，如果 sum 加上一个数已经大于目标值 target，那么 sum 加一个更大的数肯定也是大于target的。基于这个想法，我们可以对上述代码进行优化处理，具体代码如下所示。

class Solution:
    def combinationSum(self, candidates, target):
        result = []
        def backtrack(start, sum, path,candidates):
            #如果路径和等于target,将该路径加入到结果列表中
            if sum==target:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):
                #剪枝处理
                if sum + candidates[i] > target:
                    break

                #添加元素到path
                path.append(candidates[i])
                backtrack(i, sum + candidates[i], path, candidates)
                #移除添加的元素
                path.pop()
        #排序处理
        candidates.sort()
        backtrack(0,0,[],candidates)
        return result