040._combination_sum_ii.md

###40. Combination Sum II

题目:

https://leetcode.com/problems/combination-sum-ii/

难度:

Medium

Combination Sum 已经AC，做了minor change.

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        self.res = []
        self.combSum(candidates, target, 0, [])
        return self.res
        
    def combSum(self, candidates, target, start, valueList):
        length = len(candidates)
        if target == 0:
            if valueList not in self.res:
                self.res.append(valueList)
        if length == 0:
            return 
        for i in range(start, length):
            if target < candidates[i]:
                return
            self.combSum(candidates[:i] + candidates[i+1:], target - candidates[i], i, valueList + [candidates[i]])
        

以上是偷懒解法, 优化就是碰到已经碰到过的元素我们直接略过.

这里的‘碰到’是比如我们已经有它，举个例子

然后也不用担心两个相同的放不进去，因为当我们处理第一个的时候，它并没拿来跟已经放入的元素比较了，只是在和还没放入的元素比较.

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def combSum(candidates, target, start, valueList):
            length = len(candidates)
            if target < 0 :
                return
            if target == 0 :
                res.append(valueList)
            for i in range(start, length):
                if candidates[i] > target: return 
                if i > 0 and candidates[i] == candidates[i-1]: continue
                combSum(candidates[i+1:], target - candidates[i], 0, valueList + [candidates[i]])


        candidates.sort()
        res = []
        combSum(candidates, target, 0, [])
        return res
        
        

多重优化