组合总和
问题描述
给你一个无重复元素的整数数组 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
