leetcode 39 & 40 组合总数

回溯法解决

两道题的思路都是类似的,用回溯来解决问题。

39题由于数值数字没有重复的,并且每个数字可以用零到无数次,所以是一个比较简单的回溯。

40题的数字是有出现重复的,并且每个数字只可以用一次或者不用, ,所以需要先对待用的数字进行排序, 然后再在loop循环里面,排除重复的情况。

39题代码

class Solution:
    
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        def backtrace(index, tmp, target):
            if target <= 0:
                if target == 0:
                    self.res.append(tmp.copy())
            else:
                for i in range(index, len(candidates)):
                    tmp.append(candidates[i])
                    backtrace(i, tmp, target - candidates[i])
                    tmp.pop()
        backtrace(0, [], target)
        return self.res

40题代码

class Solution(object):
    def combinationSum2(self, candidates, target):
        self.res = []
        candidates.sort()
        def backtrace(index, tmp, target):
            if target == 0:
                self.res.append(tmp[:])
            elif target > 0:
                for i in range(index, len(candidates)):
                    if i > index and candidates[i] == candidates[i-1]: continue
                    tmp.append(candidates[i])
                    backtrace(i + 1, tmp, target - candidates[i])
                    tmp.pop()
        
        backtrace(0, [], target)
        return self.res

参考链接:https://www.bilibili.com/video/BV1V4411h7dU/

发表评论

电子邮件地址不会被公开。 必填项已用*标注