[40][中等][回溯] 组合总和 II

题目描述

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

• 所有数字（包括目标数）都是正整数。

• 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

题目描述

与[39][中等][回溯] 组合总和的区别在于每个数字只能使用一次. 为了防止第一个例子中[1, 1, 6]和[6, 1, 1]同时出现, 使用与39题中一样的方法, 需要先进行排序, 然后记录每一层开始的位置, 而与39层不同的是, 因为不能重复, 下一层的寻找要从之后一个位置开始.

另外数组中有重复的元素, 同一层搜索中, 两个同样元素在排序后紧邻, 搜索出来的结果也是一样的. 因此在每一层可以维护一个哈希表, 记录本层中搜索过的元素. 如果当前元素在之前搜索过, 就可以剪枝了.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        results = []
        candidates.sort()

        def dfs(path, t, start):
            if t < 0:
                return
            if t == 0:
                results.append(path[:])

            seen = set()
            for i in range(start, n):
                if candidates[i] in seen:
                    continue
                seen.add(candidates[i])
                path.append(candidates[i])
                dfs(path, t - candidates[i], i + 1)
                path.pop()

        dfs([], target, 0)
        return results