leetcode-40

leetcode-40 组合总和

题目描述:

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

注:和39题比,增加的难点主要在于有重复数字
解法一:回溯

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        candidates.sort(reverse=True)
        self.find(candidates,target,0,[])
        return self.res
    
    def find(self,candidates,target,index,path):
        if target == 0:
            self.res.append(path[:])
            return 
        prev = 0
        for i in range(index,len(candidates)):
            if candidates[i] != prev and candidates[i]<=target:
                path.append(candidates[i])
                self.find(candidates,target-candidates[i],i+1,path)
                path.pop()
                prev = candidates[i]

递归

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        candidates.sort(reverse=True)
        self.find(candidates,target,0,[])
        return self.res
    
    def find(self,candidates,target,index,path):
        if target < 0:
            return
        if target == 0:
            self.res.append(path[:])
        for i in range(index,len(candidates)):
            if i > index and candidates[i] == candidates[i-1]:
                continue
            self.find(candidates,target-candidates[i],i+1,path+[candidates[i]])

注:体会递归与回溯的区别,回溯有push和pop这个过程?

上一篇:java 打印map后的输出


下一篇:★LeetCode(39)——组合总和(JavaScript)