40. 组合总和 II

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

解法一：回溯

类似 39.组合总和

区别在于不能重复取，因此递归的起点由39题中的i变成i+1。此外还要判断是同一层递归的重复还是不同层递归，若是同一层，重复则跳过，不同层则不需要跳过，判断依据为：

i-1 >= start，若符合说明i-1与i是同一层，若还有candidates[i] == candidates[i-1]，则跳过i

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

    def backtrack(self, tmpList, candidates, remain, start):
        if remain < 0:
            return
        elif remain == 0:
            self.res.append(list(tmpList))
        else:
            for i in range(start, len(candidates)):
                #跳过重复
                if i-1 >= start and candidates[i] == candidates[i-1]:
                    continue
                #下一层递归起点为i+1
                self.backtrack(tmpList + [candidates[i]], candidates, remain - candidates[i], i+1) 

2020.3.26 因为每层对[start, n)进行递归，因此判断i-1是否在[start, n)中即可知道是否同层

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(tmp, sum, start):
            if sum > target:
                return
            elif sum == target:
                res.append(list(tmp))
                return
            for i in range(start, n):
                num = candidates[i]
                if i-1 >= start and num == candidates[i-1]:  #已经使用过了，跳过，去重
                    continue
                dfs(tmp + [num], sum + num, i+1)    #每个数字只用一次
                
        candidates.sort()
        n = len(candidates)
        res = []
        dfs([], 0, 0)
        return res