LeetCode 热题 100 39. 组合总和

LeetCode 热题 100 | 39. 组合总和

大家好，今天我们来解决一道经典的算法题——组合总和。这道题在 LeetCode 上被标记为中等难度，要求给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。下面我将详细讲解解题思路，并附上 Python 代码实现。

---

问题描述

给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素互不相同
• 1 <= target <= 40

---

解题思路

核心思想

1. 回溯法：

   • 回溯法是一种通过递归枚举所有可能解的方法。
   • 在生成组合总和的过程中，我们逐个选择数组中的数字，并将其加入当前组合中。
   • 为了避免重复选择同一个数字，我们需要记录当前选择的数字和剩余的目标值。

2. 递归终止条件：

   • 当当前组合的和等于目标值时，说明已经生成了一个有效的组合，将其加入结果列表中。
   • 当当前组合的和大于目标值时，说明当前组合无效，需要回溯。

3. 递归过程：

   • 遍历数组中的每个数字，从当前索引开始，避免重复选择。
   • 将当前选择的数字加入当前组合，并递归生成下一个数字的组合。
   • 在递归返回时，移除当前组合中的最后一个数字（回溯）。

---

Python代码实现

class Solution:def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""result = []path = []def backtracking(start, target):if target == 0:result.append(path[:])returnif target < 0:returnfor i in range(start, len(candidates)):path.append(candidates[i])backtracking(i, target - candidates[i])path.pop()backtracking(0, target)return result# 测试示例
solution = Solution()# 示例 1
candidates1 = [2, 3, 6, 7]
target1 = 7
print(solution.combinationSum(candidates1, target1))  # 输出: [[2, 2, 3], [7]]# 示例 2
candidates2 = [2, 3, 5]
target2 = 8
print(solution.combinationSum(candidates2, target2))  # 输出: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]# 示例 3
candidates3 = [2]
target3 = 1
print(solution.combinationSum(candidates3, target3))  # 输出: []

---

代码解析

1. 回溯函数 backtracking：

   • 参数：
     • start：当前递归的起始索引，用于避免重复选择同一个数字。
     • target：剩余的目标值。
   • 当 target == 0 时，说明已经生成了一个有效的组合，将其加入结果列表 result。
   • 当 target < 0 时，说明当前组合无效，需要回溯。
   • 遍历数组中的每个数字，从 start 开始，避免重复选择。
   • 将当前选择的数字加入 path，并递归生成下一个数字的组合。
   • 在递归返回时，移除 path 中的最后一个数字（回溯）。

2. 结果列表 result：

   • 用于存储所有生成的有效组合。

3. 路径列表 path：

   • 用于存储当前递归过程中正在构建的组合。

---

复杂度分析

• 时间复杂度：O(n^k)，其中 n 是数组的长度，k 是组合的平均长度。在最坏情况下，我们需要枚举所有可能的组合。
• 空间复杂度：O(k)，递归调用栈的深度为 k，同时需要存储当前组合 path。

---

示例运行

示例 1

输入：candidates = [2, 3, 6, 7], target = 7
输出：[[2, 2, 3], [7]]

示例 2

输入: candidates = [2, 3, 5], target = 8
输出: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

示例 3

输入: candidates = [2], target = 1
输出: []

---

总结

通过回溯法，我们可以高效地生成所有可能的组合总和。这种方法利用递归枚举所有可能的组合，并通过回溯避免重复选择。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！