39. 组合总和
3 min
题目
解法：回溯算法
思路
第一段：使用回溯算法（DFS）枚举所有可能的组合，通过递归和剪枝搜索解空间。
第二段：算法正确性基于以下不变量：每次递归从 start 位置开始遍历，保证生成的组合是非递减序列，避免重复组合；当 target 减至 0 时记录有效解，当 target 小于 0 时剪枝。由于数字可重复使用，递归时保持 start 为 i 而非 i+1，确保能多次选择同一元素。
第三段：
- Step 1: 定义 dfs 函数，参数为 candidates、剩余目标值 target 和起始索引 start
- Step 2: 当 target == 0 时，将当前路径 path 加入结果集 res
- Step 3: 当 target < 0 时直接返回，进行剪枝
- Step 4: 从 start 遍历到 candidates 末尾，将当前元素加入 path
- Step 5: 递归调用 dfs，target 减去当前元素，start 保持为 i
- Step 6: 回溯，从 path 中弹出当前元素
复杂度
- 时间复杂度: O(N^{target/min(candidates)})，其中 N 是 candidates 的长度。最坏情况下需要探索所有可能的组合，呈指数级增长。
- 空间复杂度: )，递归调用栈的最大深度，用于存储当前路径。
代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& candidates, int target, int start){
if(target == 0){
res.push_back(path);
return;
}
if(target < 0)
return;
for(int i = start; i < candidates.size(); i++){
path.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i);
path.pop_back();
}
}
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& candidates, int target, int start){
if(target == 0){
res.push_back(path);
return;
}
if(target < 0)
return;
for(int i = start; i < candidates.size(); i++){
path.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0);
return res;
}
};