Leetcode 40. Combination Sum II

Description: Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Link: 40. Combination Sum II

Examples:

Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

思路: 这道题和39的差别就是不可对同一个数字重复挑选，且candidates中不是每个数字都是unique的，有相同的。所以我们可以用i+1的传入来解决重复挑选，如果candidates[i] == candidates[i-1]，i-1已经做过一次搜索了，所以就不必要对i再重复一次，否则结果会duplicate。

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

日期: 2021-04-21  刷题的确让人进步