40. 组合总和 II¶

难度：中等

题目¶

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

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

注意： 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

输出:
[
[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

Reference

题解¶

由于每个数字只能使用一次，并且不能返回重复的组合，因此，可以统计每个数字的个数，逐个数字进行深度优先的搜索。搜索的终止条件为：

当前的和等于目标值，此时相当于我们找到了一个有效的解，将其记录下来。
当前的和大于目标值，此时说明当前的组合不可能是有效的解，直接返回。
当前的数字已经超过了目标值，直接返回。

在剩余情况下，我们需要考虑当前数字的个数\(n\)，逐个判断使用当前数字\(0\)次到\(n\)次的情况。如果使用某一次后找到了有效解，就不再需要继续搜索其他次数。一种思路是从1逐个地考虑到\(n\)。

class Solution:
    def dfs(
        self, k: int, end: int, counter: Dict[int, int], target: int,
        current_seq: List[int], results: List[List[int]]
    ):
        if target == 0:
            results.append(current_seq)
            return True
        if k > end or target < 0:
            return False
        v = counter.get(k, 0)
        for number in range(min(v, target // k) + 1):
            if self.dfs(
                k + 1, end, counter, target - k * number,
                current_seq + [k] * number, results
            ):
                break
        return False

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        counter = Counter([_ for _ in candidates if _ <= target])
        result = []
        self.dfs(1, target, counter, target, [], result)
        return result

如上方法会导致大量无效迭代，可以通过只在出现的数字中进行寻找，减少无效的搜索。

class Solution:
    def dfs(
        self, k_idx: int, k_list: List[int], counter: Dict[int, int], target: int,
        current_seq: List[int], results: List[List[int]]
    ):
        if target == 0:
            results.append(current_seq)
            return True
        if k_idx >= len(k_list) or target < 0:
            return False
        k = k_list[k_idx]
        v = counter.get(k, 0)
        for number in range(min(v, target // k) + 1):
            if self.dfs(
                k_idx + 1, k_list, counter, target - k * number,
                current_seq + [k] * number, results
            ):
                break
        return False

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        counter = Counter([_ for _ in candidates if _ <= target])
        result = []
        k_list = [*counter]
        self.dfs(0, k_list, counter, target, [], result)
        return result

40. 组合总和 II¶

题目¶

题解¶

评论