LeetCode【0039】组合总和

1 中文题目

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

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

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

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

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

提示：

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

---

2 求解方法：回溯法

2.1 方法思路

方法核心

• 使用回溯算法解决组合问题
• 通过排序和剪枝优化搜索效率
• 维护当前路径和起始位置

实现步骤

（1）预处理：

• 对候选数组进行排序
• 初始化结果列表

（2）回溯过程：

• 记录当前路径和剩余目标值
• 从指定位置开始搜索
• 进行剪枝优化
• 维护搜索状态

（3）状态管理：

• 添加当前数字到路径
• 递归搜索剩余目标
• 回溯删除当前数字
• 继续搜索其他可能

方法示例

输入示例：candidates = [2,3,6,7], target = 7执行过程：1. 首先排序（本例已排序）
2. 开始回溯搜索：第一层递归：从2开始
- 选择2：[2], target=5第二层递归：- 选择2：[2,2], target=3第三层递归：- 选择2：[2,2,2], target=1- 回溯到[2,2]- 选择3：[2,2,3], target=0 （找到解）- 回溯到[2,2]- 回溯到[2]- 选择3：[2,3], target=2第三层递归：- 选择2：[2,3,2], target=0 （找到解）- 回溯到[2,3]- 回溯到[2]
- 回溯到[]
- 选择3：[3], target=4... （类似过程）
- 选择6：[6], target=1- 剪枝（1<6）
- 选择7：[7], target=0 （找到解）最终结果：[[2,2,3], [2,3,2], [7]]

2.2 Python代码

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:# 对候选数组进行排序，便于剪枝candidates.sort()# 存储所有符合条件的组合result = []def backtrack(target: int, temp_list: List[int], start: int) -> None:"""回溯函数target: 当前还需要的和temp_list: 当前已选择的数字列表start: 本次搜索的起始位置"""# 如果目标值为0，说明当前组合符合要求if target == 0:result.append(temp_list[:])return# 从start开始遍历候选数组for i in range(start, len(candidates)):# 剪枝：如果当前数字已经大于目标值，后面的数字更大，直接breakif candidates[i] > target:break# 将当前数字加入临时列表temp_list.append(candidates[i])# 递归调用，注意target减去当前数字，start保持在i（因为可以重复使用）backtrack(target - candidates[i], temp_list, i)# 回溯，移除最后加入的数字temp_list.pop()# 从0开始回溯搜索backtrack(target, [], 0)return result

2.3 复杂度分析

• 时间复杂度：$O(N^{T/M})$，N是candidates数组的长度，T是目标值target，M是candidates中的最小值
  • 实际复杂度因剪枝而降低
• 空间复杂度：$O(T/M)$
  • 递归调用栈的深度

---

3 题目总结

题目难度：中等
数据结构：数组
应用算法：回溯