边工作边刷题：70天一遍leetcode: day 34-3

Combination Sum II

要点
错误点：

• 对于unlimited那题，因为不可能有负数和正数（这样会出现无限解），所以target<0是失败条件
• 因为已经排好序了，所以target==0以后就应该return
• 注意next的index是i而不是start，这个很容易错写成start，另外unlimited这题是可重用的，所以仍然从当前的i开始
• 这题本身指明都为正数，如果不target<0 return会TLE，实际对于limited这题，有负数也是可以做的

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def dfs(candidates, start, target, res, solutions):
            n = len(candidates)
            if target==0:
                resCp = list(res)
                solutions.append(resCp)
                return
                
            if start>=n or target<0:
                return
            
            for i in range(start, n):
                if i!=start and candidates[i]==candidates[i-1]: continue
                res.append(candidates[i])
                dfs(candidates, i+1, target-candidates[i], res, solutions)
                res.pop()
        
        candidates = sorted(candidates)
        res = []
        solutions = []
        dfs(candidates, 0, target, res, solutions)
        return solutions