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

【题目解析】

思路

解决这个问题的方法是使用回溯算法，一个经典的算法，用于在解空间树中搜索所有可能的解。以下是解题的步骤：

排序：首先对数组进行排序，这样做可以帮助我们更容易地跳过重复的元素，避免生成重复的组合。
回溯搜索：从数组的开始进行深度优先搜索，探索所有可能的组合。
剪枝：为了避免在结果集中出现重复的组合，我们需要在每一层递归中跳过相同的元素。
递归终止条件：当组合中数字的和等于目标值时，将其添加到结果集中；如果和大于目标值，停止递归。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 首先对候选数字进行排序，这样可以帮助我们跳过重复的组合
        candidates.sort()
        # 这是最终的结果列表
        res = []
        
        # 定义回溯函数
        def backtrack(start, path, target):
            # 如果当前路径的数字和等于目标值，将其添加到结果列表中
            if target == 0:
                res.append(path)
                return
            # 如果当前路径的数字和大于目标值，停止当前路径的探索
            if target < 0:
                return
            
            # 遍历剩余的数字
            for i in range(start, len(candidates)):
                # 跳过重复的数字，以避免重复的组合
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                # 如果当前数字已经大于目标值，由于数组已排序，后面的数字也不可能满足条件了
                if candidates[i] > target:
                    break
                # 选择当前数字，并继续递归探索剩下的数字
                backtrack(i + 1, path + [candidates[i]], target - candidates[I])
        
        # 从索引0的位置开始回溯搜索
        backtrack(0, [], target)
        return res

执行

image.png

【总结】

组合总和 II问题要求从一个可能含有重复数字的数组中找出所有唯一的组合，这些组合的数值之和等于给定的目标值。这个问题在算法设计和编程实践中极具挑战性，因为它不仅要求我们找到所有可能的解决方案，还要避免在结果集中生成重复的组合。

适用场景

这种类型的回溯算法特别适用于以下情境：

决策问题：需要从一系列选项中做出一系列决策，达到某个目标条件的问题。
排列组合问题：需要找出所有可能的排列或组合，特别是当元素可以重复选择，但结果必须唯一时。
约束满足问题：在满足一定约束条件下，寻找所有可能解的问题。

解决算法：回溯算法

组合总和 II问题通过回溯算法进行求解。回溯算法是一种通过探索所有可能路径来找到所有解决方案的方法。对于组合总和 II问题，回溯算法的关键特点包括：

选择和撤销选择：在探索解空间时，算法需要不断地在当前路径上添加新的数字（选择），如果发现当前路径不能达到目标，就撤销最近的选择，回溯到之前的状态。
避免重复：由于输入数组可能包含重复的数字，算法需要额外的逻辑来避免生成重复的组合。这通常通过跳过相同的元素来实现。
剪枝：为了提高效率，算法在某些情况下会提前终止探索，这称为剪枝。例如，当当前组合的和已经超过目标值时，就没有继续探索的必要了。

时间复杂度与空间复杂度

时间复杂度：回溯算法的时间复杂度通常较难精确计算，因为它依赖于解空间的大小。在最坏情况下，时间复杂度接近于O(2^N)，N是数组长度。但通过剪枝和避免重复路径，实际的时间复杂度通常会低于此值。
空间复杂度：空间复杂度主要由递归调用栈和用于存储中间结果的空间组成。最坏情况下的空间复杂度为O(N)，N为递归栈的最大深度。

总结

组合总和 II问题展示了回溯算法在处理组合搜索问题中的强大能力，尤其是涉及到避免重复解和剪枝优化时。掌握这一算法不仅对于解决特定问题类型至关重要，也能够提升我们在更广泛领域内解决问题的能力。通过实际编码实践，我们可以更深刻地理解回溯算法的工作原理和应用场景，进而在面对复杂的算法问题时，能够设计出更加高效、精确的解决方案。

题目链接

组合总和 II

40. 组合总和 II