40. 组合总和 II

Difficulty
Medium
Tags
回溯
URL
https://leetcode-cn.com/problems/combination-sum-ii/
Star
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
通过次数192,750提交次数307,364

法1 回溯

思路
与
🖥️
39. 组合总和 相比，本题多了如下条件：
  • 每个元素只能出现一次
  • 备选数组中有重复数字
对于组合问题中的除非数字，采用排序 + if i > start and nums[i] == nums[i-1] : continue 的策略
题解 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        candidates.sort()
        self.backtrack(path=[], target=target, candidates=candidates, start=0)
        return self.res

    def backtrack(self, path, target, candidates, start):
        if sum(path) == target:
            self.res.append(path[:])
            return
        elif sum(path) >= target:
            return
        
        for i in range(start, len(candidates)):
            if i > start and candidates[i]== candidates[i-1]:
                continue
            path.append(candidates[i])
            self.backtrack(path, target, candidates, i+1)
            path.pop()