39. 组合总和 

如下树形结构如下：

选取第二个数字5之后，剩下的数字要从5、3中取数了，不能再取2了，负责组合就重复了，注意这一点，自己做的时候没想明白这一点

如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合

代码如下：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result= []
        path = []
        self.backtracking(candidates,0,target,path,result)
        return result

    def backtracking(self,candidates,startIndex,target,path,result):
        if sum(path) > target:
            return
        if sum(path) == target:
            result.append(path[:])
            return

        for i in range(startIndex,len(candidates)):
            path.append(candidates[i])
            self.backtracking(candidates,i,target,path,result)
            path.pop()
        

剪枝优化

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result= []
        path = []
        candidates.sort() #列表要排序
        self.backtracking(candidates,0,target,path,result)
        return result

    def backtracking(self,candidates,startIndex,target,path,result):
       
        if sum(path) == target:
            result.append(path[:])
            return

        for i in range(startIndex,len(candidates)): #剪枝优化都是在for循环中做优化
            if sum(path) > target: #如果组合的和比目标值要大就跳出循环
                break 
            path.append(candidates[i])
            self.backtracking(candidates,i,target,path,result)
            path.pop()
        

自己做法：

考虑到把数组排序了，那么在收集数组的时候，也是按照排序来的，所以可以直接return结果：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.backtrack(candidates,target,0,[],result)
        return result
    
    def backtrack(self,candidates,target,startIndex,path,result):
        if path in result: #直接return
            return
        if sum(path) == target:
            result.append(path[:])
            return
        
        for i in range(startIndex,len(candidates)):
            if sum(path) > target:
                continue
            path.append(candidates[i])
            self.backtrack(candidates,target,i+1,path,result)
            path.pop()        

代码随想录：

class Solution:


    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            if i > startIndex and candidates[i] == candidates[i - 1]:
                continue

            if total + candidates[i] > target:
                break

            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i + 1, path, result)
            total -= candidates[i]
            path.pop()

    def combinationSum2(self, candidates, target):
        result = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, [], result)
        return result

使用used：

选择过程树形结构如图所示：

class Solution:


    def backtracking(self, candidates, target, total, startIndex, used, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            # 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字
            if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:
                continue

            if total + candidates[i] > target:
                break

            total += candidates[i]
            path.append(candidates[i])
            used[i] = True
            self.backtracking(candidates, target, total, i + 1, used, path, result)
            used[i] = False
            total -= candidates[i]
            path.pop()

    def combinationSum2(self, candidates, target):
        used = [False] * len(candidates)
        result = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, used, [], result)
        return result