组合总和II

40. 组合总和 II - 力扣（LeetCode）

问题简述

给定一个候选人编号的集合 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 

思路

• 递归+回溯模板；

• 代码细节：

  • 每个数字只用一次；

  • 组合去重；

Python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        ret = []

        def dfs(s, start, tmp):

            if s >= target:
                if s == target:
                    ret.append(tmp[:])
                return
            
            for i in range(start, len(candidates)):
                # 注意这里是 i > start（每个数字取一次），而不是 i > 0（每种数字取一次）
                if i > start and candidates[i] == candidates[i - 1]:
                    continue

                tmp.append(candidates[i])
                dfs(s + candidates[i], i + 1, tmp)  # i + 1 表示下一个开始取，即每个数字只使用一次
                tmp.pop()

        candidates.sort()  # 排序
        dfs(0, 0, [])
        return ret

相关问题

• 39. 组合总和 - 力扣（LeetCode）