39. 组合总和

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def __init__(self):
        self.sum = 0
        self.path,self.result = [],[]
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort() # 为方便后续剪枝，先排序。
        def combinationSum_(candidates,target,sum,startindex) -> List[List[int]]:
            # 多叉树 回溯 ，解决 组合问题。
            if self.sum > target: return 
            if self.sum == target:
                self.result.append(self.path.copy())
                return 
            for i in range(startindex,len(candidates)):     
                if self.sum + candidates[i]>target: break   # 加入 右剪枝操作。
                self.path.append(candidates[i])
                self.sum += candidates[i]
                combinationSum_(candidates,target,self.sum,i)  
                reduce = self.path.pop()
                self.sum -= reduce 
            return self.result
        return combinationSum_(candidates,target,self.sum,0)