LeetCode第40题：组合总和ll【python 40/1000】

本文主要是介绍LeetCode第40题：组合总和ll【python 40/1000】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode的第40题“组合总和II”要求在一个可能包含重复元素的整数数组中找出所有的组合，这些组合中的元素之和等于给定的目标数。这些组合中的每个数字在每个组合中只能使用一次。本文将探讨三种不同的方法来解决这个问题，并分析它们的时间和空间复杂度。

题目描述

输入：一个整数数组 candidates 和一个目标数 target。

输出：所有唯一的组合，使得组合中数字的总和为 target。数组中的每个数字在每个组合中只能使用一次。

示例：

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

方法一：回溯法

解题步骤

使用回溯法搜索所有可能的组合。为避免重复，先对数组进行排序，然后在递归过程中跳过相同的元素。

排序：首先对数组进行排序，这样可以方便后续步骤跳过重复的元素。
回溯：设计一个回溯函数，用于递归地探索所有可能的组合。
剪枝：在回溯过程中，如果当前组合的和已经大于目标值 target，则停止进一步探索。
跳过重复元素：在同一层递归中，如果一个数和前一个数相同，则跳过这个数，以避免生成重复的组合。

代码实现

from typing import Listdef combinationSum2(candidates: List[int], target: int) -> List[List[int]]:def backtrack(start: int, target: int, path: List[int]):# 当前路径和已经等于目标值，将其添加到结果中if target == 0:res.append(path.copy())return# 遍历起始位置到数组结束for i in range(start, len(candidates)):# 跳过同一树层使用过的元素，避免重复组合if i > start and candidates[i] == candidates[i - 1]:continue# 如果当前元素已大于目标值，则后续元素无需考虑if candidates[i] > target:break# 选择当前值，继续探索path.append(candidates[i])# 递归调用，注意新的起点为 i+1，因为每个数字在每个组合中只能使用一次backtrack(i + 1, target - candidates[i], path)# 撤销选择path.pop()# 结果列表res = []# 先排序，方便后续操作candidates.sort()# 从索引0开始，目标值为target的回溯backtrack(0, target, [])return res# 示例调用
print(combinationSum2([10,1,2,7,6,1,5], 8))  # 输出: [[1,1,6], [1,2,5], [1,7], [2,6]]

算法分析

时间复杂度：O(2^N)，其中 N 是数组 candidates 的长度。
空间复杂度：O(N)，递归栈的深度最大为 N。

方法二：动态规划

解题步骤

初始化动态规划列表：创建一个列表 dp，其中 dp[i] 是一个集合，存储所有加和为 i 的组合。
填充动态规划列表：遍历每个数字，并更新 dp 列表，使其包括当前数字能够形成的所有新组合。
处理重复元素：为防止同一数字重复使用，从目标值向下更新 dp 列表。
组合去重：使用集合而不是列表来存储每个 dp[i] 的组合，这样可以自动去除重复的组合。

代码实现

下面是完整的代码实现，包括详细的注释：

from typing import Listdef combinationSum2(candidates: List[int], target: int) -> List[List[int]]:candidates.sort()  # 排序以方便去重dp = [set() for _ in range(target + 1)]dp[0].add(tuple())  # 初始化，和为0的组合自然是空组合for num in candidates:# 从后向前更新dp数组，防止同一数字被重复使用for t in range(target, num - 1, -1):for prev in dp[t - num]:dp[t].add(prev + (num,))# 将每个组合转换为列表形式，以符合题目要求return [list(comb) for comb in dp[target]]# 示例调用
print(combinationSum2([10,1,2,7,6,1,5], 8))
# 输出: [[1,1,6], [1,2,5], [1,7], [2,6]]

代码说明

初始化：dp 列表初始化包含目标和 target + 1 个空集合，用于存储达到每个和的可能组合。
动态更新：遍历 candidates 每个元素，并逆序更新 dp，这样可以保证每个元素只在其应在的组合中使用一次。
组合存储：使用元组来存储组合中的元素，元组可以被集合自动去重，这避免了生成重复的组合。
结果转换：最后将存储在 dp[target] 中的组合元组转换为列表，以符合题目输出格式的要求。

算法分析

时间复杂度：O(NTK)，其中 N 是数组长度，T 是目标值，K 是平均每个 dp 元素的集合大小。
空间复杂度：O(T*K)，存储所有可能组合的空间。

方法三：优化的回溯法

解题步骤

排序：首先对数组进行排序，这有助于后续的剪枝操作和跳过重复项。
定义回溯函数：创建一个用于回溯的辅助函数，该函数将尝试构建满足条件的组合。
剪枝优化：在回溯的每一步中，如果当前组合的总和加上当前数字已经超过目标值，则停止该路径的进一步探索。
跳过重复元素：在同一层递归中，如果一个数字与前一个数字相同，则跳过当前数字，以避免产生重复的组合。
回溯逻辑实现：
- 如果组合的和等于目标值，将其添加到结果列表中。
- 否则，继续探索加入更多的数字。

代码实现

from typing import Listdef combinationSum2(candidates: List[int], target: int) -> List[List[int]]:def backtrack(start: int, target: int, path: List[int]):# 目标金额减到0，添加路径到结果if target == 0:res.append(path.copy())returnif 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# 选择当前数，并递归探索path.append(candidates[i])backtrack(i + 1, target - candidates[i], path)path.pop()  # 撤销选择，回溯candidates.sort()  # 排序是剪枝的前提res = []backtrack(0, target, [])return res# 示例调用
print(combinationSum2([10,1,2,7,6,1,5], 8))
# 输出: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

代码说明

排序：对数组进行排序，以便可以有效地跳过重复项并进行剪枝。
回溯函数 backtrack：
- start：当前选择的起始索引，防止重复使用同一数字。
- target：剩余目标值，用于判断当前路径的可行性。
- path：当前路径，记录已选择的数字。
跳过重复元素：通过在循环中添加判断条件，跳过之前已经使用过的并且与当前数字相同的数字。
剪枝：在每次递归调用前检查，如果当前数字大于target，则后续数字都不需要再考虑；如果target减当前数字小于0，则当前路径不可能为解。

算法分析

时间复杂度：O(2^N)，其中 N 是数组 candidates 的长度。尽管有剪枝，但在最坏情况下，时间复杂度可能接近2的N次方。
空间复杂度：O(N)，递归栈的深度最大为 N，这是由于递归深度与数组长度成正比。

结论

特征	回溯法	动态规划	优化的回溯法
时间复杂度	O(2^N)	O(N * T * K)	O(2^N)
空间复杂度	O(N)	O(T * K)	O(N)
优势	- 直接且易于理解 - 灵活处理复杂约束	- 不重复计算子问题 - 状态存储使得查找有效率	- 通过剪枝减少不必要的计算 - 跳过重复元素提高效率
劣势	- 可能产生大量重复计算 - 需要手动处理重复结果	- 空间复杂度较高 - 初始化和填充dp表可能复杂	- 逻辑比基本回溯复杂 - 依然可能达到2^N的时间复杂度
适用场景	- 数据规模较小 - 需要直观展示所有可能结果	- 需要频繁查询组合结果 - 合适处理不同但相关的多次查询	- 数据规模中等 - 要求避免重复和高效率处理