06、组合总和
大约 6 分钟数据结构算法算法基地面试回溯刷题程序厨校招社招
你好，我是厨子，今天给大家说一个回溯的经典问题，组合总和
https://leetcode.cn/problems/combination-sum/
题目描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
示例 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 <= 302 <= candidates[i] <= 40candidates的所有元素互不相同1 <= target <= 40
组合总和的特点
与普通组合的区别
普通组合：
- 每个数字只能用一次
- [1,2,3] 中选 2 个：[1,2], [1,3], [2,3]
组合总和（本题）：
- 每个数字可以无限次使用
- [2,3] 凑 8：[2,2,2,2], [2,3,3], [3,3,2] (去重后)
- 关键：同一个数可以选多次！
问题本质
问题转化：
给定硬币面值 [2,3,6,7]
凑出 7 元，有多少种方案？
每种硬币可以用无限次
这是一个完全背包问题的变种
也是一个典型的回溯搜索问题
解题思路
核心思想
关键点：
1. 数字可以重复选择
2. 要找出所有组合（不是排列）
3. 需要避免重复的组合
例如：[2,3,3] 和 [3,2,3] 是同一个组合
回溯策略：
状态：
- path: 当前组合
- sum: 当前组合的和
- start: 从哪个位置开始选择
选择：
- 可以选择 candidates[start] 到 candidates[n-1]
- 每个数字可以选多次
终止条件：
- sum == target：找到一个解
- sum > target：当前路径不可行
代码实现
基础版本
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
backtrack(candidates, target, 0, 0);
return result;
}
private:
*/
void backtrack(vector<int>& candidates, int target, int sum, int start) {
// 终止条件：找到一个解
if (sum == target) {
result.push_back(path);
return;
}
// 终止条件：超过目标值，剪枝
if (sum > target) {
return;
}
// 遍历选择列表
for (int i = start; i < candidates.size(); i++) {
// 做选择
path.push_back(candidates[i]);
sum += candidates[i];
// 递归：注意 start = i（可以重复选择）
backtrack(candidates, target, sum, i);
// 撤销选择
path.pop_back();
sum -= candidates[i];
}
}
};
优化版本（提前剪枝）
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
// 排序：方便剪枝
sort(candidates.begin(), candidates.end());
backtrack(candidates, target, 0, 0);
return result;
}
private:
void backtrack(vector<int>& candidates, int target, int sum, int start) {
// 找到解
if (sum == target) {
result.push_back(path);
return;
}
// 遍历选择列表
for (int i = start; i < candidates.size(); i++) {
// 剪枝：如果当前数字已经让 sum 超过 target
// 由于数组已排序，后面的数字更大，也会超过
// 可以直接 break
if (sum + candidates[i] > target) {
break; // 不是 continue，是 break！
}
// 做选择
path.push_back(candidates[i]);
// 递归：注意 start = i（可以重复）
backtrack(candidates, target, sum + candidates[i], i);
// 撤销选择
path.pop_back();
}
}
};
优化说明：
排序 + 剪枝：
例子：candidates=[2,3,6,7], target=7
排序后：[2,3,6,7]
当 sum=6, 选择 6:
sum + 6 = 12 > 7，break
后面的 7 更大，也不用尝试了
不剪枝：
还要尝试 7，发现 sum + 7 = 13 > 7
剪枝后：
直接 break，节省一次递归
时间复杂度: O(S)，S 是所有可行解的长度之和
空间复杂度: O(target) - 递归栈深度最多为 target/min(candidates)
关键点详解
在这里对大家易错的点做下总结
关键点1：为什么 start = i 而不是 i + 1？
对比：
LeetCode 77（组合）：
- 每个数字只能用一次
- [1,2] 选过后，不能再选 1 或 2
- 递归时 start = i + 1
LeetCode 39（组合总和）：
- 每个数字可以用多次
- [2] 选过后，还可以再选 2
- 递归时 start = i（保持当前位置）
例子：candidates=[2,3], target=6
start = i:
[2] → [2,2] → [2,2,2] ✓
[2] → [2,3] ✗
[3] → [3,3] ✓
start = i+1:
[2] → [3] → 结束（没有 [2,2,2]）✗
[3] → 结束（没有 [3,3]）✗
关键点2：如何避免重复？
问题：[2,3,3] 和 [3,2,3] 是同一个组合
解决：每次只选择 >= start 的数字
例子：candidates=[2,3], target=8
搜索树（正确）：
[]
/ \
2 3
/ \ \
2 3 3
| | |
2 3 3
生成：[2,2,2,2], [2,3,3], [3,3,2] ✗
等等，[3,3,2] 怎么来的？
仔细看：
3 → 3 → ...
当 start=1（选 3）后
递归时 start 仍然是 1
可以选 candidates[1]=3（自己）
但不能选 candidates[0]=2（因为 i 从 start 开始）
所以不会出现 [3,2]，只会出现 [3,3]
正确结果：[2,2,2,2], [2,3,3], [3,3] ✗
再次检查：target=8
[2,2,2,2]: 2+2+2+2=8 ✓
[2,3,3]: 2+3+3=8 ✓
[3,3]: 3+3=6 ✗ (不等于 8)
实际结果：[2,2,2,2], [2,3,3]
关键点3：排序+剪枝的威力
不排序：
candidates=[7,6,3,2], target=7
要尝试：
7 ✓
6 → 1 (没有 1)
6 → 2 (没有)
3 → ...
2 → ...
排序后：
candidates=[2,3,6,7], target=7
要尝试：
2 → ...
3 → ...
6 → 当 sum=0+6=6 时，再选 6: 6+6=12>7，break
后面的 7 更大，不用试了
7 ✓
效果：
不排序：尝试很多无效路径
排序后：提前 break，减少递归次数
