0.总结

• 本题的关键就是：避免重复。先排序，再对重复的进行while循环，避免重复搜索。

1.题目

2.思想

这个问题的关键在于：如果有连续的数字相等，那么很多都是重复的操作，该怎么避免这种重复？比如

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
30

这种样例
其实结合一个简单sample[1,1,1,1,1]仔细思考一下，如果我们当前的tmp是[1,1],那么为了避免重复搜索，我另外一轮的搜索就应该是[1,x]这个x!=1。这个代码的实现如下：

 # 这个数不放， 放弃与当前值相等的值
        i = pos+1 # 下一个数
        while(i<n) :
            print(i)
            if nums[i] == nums[pos]:
                i+=1                
            else:
                break

3. 代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        pos = 0
        res = set()
        tmp = []
        candidates.sort()
        pre = None
        # for i in range(len(candidates)):
        #     if candidates[i] == pre:                
        #         continue
        #     pre = candidates[i]
        self.dfs(candidates,len(candidates),pos,target,tmp,res)
        return list(res)

    def dfs(self,nums,n,pos,target,tmp,res):        
        if sum(tmp) == target:
            res.add(tuple(copy.deepcopy(tmp)))
            return 
        if sum(tmp) > target:
            return 
        if sum(tmp) + sum(nums[pos::]) < target: # 如果当前值的数和 与 后面的和都不到target
            return 
        if pos >= n:
            return
        
        # 这个数放进去
        tmp.append(nums[pos])
        self.dfs(nums,n,pos+1,target,tmp,res)
        tmp.pop()

        # 这个数不放， 放弃与当前值相等的值
        i = pos+1 # 下一个数
        while(i<n) :
            print(i)
            if nums[i] == nums[pos]:
                i+=1                
            else:
                break
        self.dfs(nums,n,i,target,tmp,res)