作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
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 List def 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 List def 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 List def 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()) 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 # 选择当前数，并递归探索 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的时间复杂度 |
| 适用场景 | - 数据规模较小 - 需要直观展示所有可能结果 |
- 需要频繁查询组合结果 - 合适处理不同但相关的多次查询 |
- 数据规模中等 - 要求避免重复和高效率处理 |
这三种方法各有优缺点，回溯法是解决这类问题的经典方法，提供了直观的搜索策略和容易理解的结构；动态规划适用于需要重复利用之前结果的情况，但空间消耗相对较大；优化的回溯法在回溯法的基础上通过剪枝减少不必要的计算，提高了效率。在实际应用中，可以根据问题的具体情况和性能需求选择最适合的方法。
欢迎关注微信公众号 数据分析螺丝钉
