2019-05-26 LeetCode40. 组合总和 II

使用排序，set去重解决重复问题，不过超时，因为没有剪枝

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        t,res=len(candidates),[]
        res_set=set()
        for i in range(1<<t):
            tmp,line=[],0
            for j in range(t):
                if i&(1<<j):
                    c=candidates[j]
                    tmp.append(c)
                    line+=c
            if line==target:
                tu=tuple(tmp)
                if not tu in res_set:
                    res_set.add(tu)
                    res.append(tmp)
        return res  

回溯+剪枝 18min image.png

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res=[]
        self.dfs(candidates,target,0,[],res)
        return res

    def dfs(self, nums, target, start, path, res):
        p=sum(path)
        if p == target: res.append(path+[])
        if p < target:
            for i in range(start,len(nums)):
                if i!= start and nums[i]==nums[i-1]:continue
                path.append(nums[i])
                self.dfs(nums,target,i+1,path,res)
                path.pop()

改进一点，在路径上求和

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res=[]
        self.dfs(candidates,target,0,[],res)
        return res

    def dfs(self, nums, target, start, path, res):
        if 0 == target: res.append(path+[])
        if 0 < target:
            for i in range(start,len(nums)):
                if i!= start and nums[i]==nums[i-1]:continue
                path.append(nums[i])
                self.dfs(nums,target-nums[i],i+1,path,res)
                path.pop()

在上一篇子集迭代的方法上改进，由于超过target的子集被剪枝了，所以l在这里会变，如果与前一个不等，那自然每一个子集+1，如果等的话，个数要进行统计

        candidates.sort()
        res=[[]]
        result=[]
        for i in range(len(candidates)):
            cnt = 0
            if i==0 or candidates[i]!=candidates[i-1]:l=len(res)
            for j in range(len(res)-l,len(res)):
                u=res[j]+[candidates[i]]
                s=sum(u)
                if s<=target:
                    res.append(u)
                    cnt+=1
                if s==target:result.append(u)
                l=cnt
        return result

从后往前，动态规划。这里因为candidates里有重复数字，所以需要用set进行去重

class Solution:
    def combinationSum2(self, candidates, target):
        candidates.sort()
        dp = [set() for i in range(target+1)]
        dp[0].add(())
        for c in candidates:
            for i in range(target,c-1,-1):
                for pre in dp[i-c]:
                    dp[i].add(pre+(c,))
        return list(dp[-1])