回溯
- 思路：
- 定义递归函数 dfs(candidates, target, idx)，表示当前 candidates 在 idx 位，还剩 target 需要组合；
- 递归终止条件：
- target <= 0；
- target == 0 时，将该组合存入结果数组；
- candidates 元素已经用完，idx = candidates.size()；
- target <= 0；
- 在当前函数中，可以：
- 跳过 candidates[idx] 元素进行组合，即 dfs(candidates, target, idx + 1) ；
- 也可以使用 candidates[idx] 元素进行组合（因为可以使用重复元素），即 dfs(candidates, target - candidates[idx], idx)
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0);
return result;
}
private:
void dfs(std::vector<int>& candidates, int target, int idx) {
if (idx == candidates.size()) {
return;
}
if (target == 0) {
result.emplace_back(item);
return;
}
dfs(candidates, target, idx + 1);
if (target - candidates[idx] >= 0) {
item.emplace_back(candidates[idx]);
dfs(candidates, target - candidates[idx], idx);
item.pop_back();
}
}
private:
std::vector<std::vector<int>> result;
std::vector<int> item;
};文章来源地址https://www.toymoban.com/news/detail-801261.html
文章来源：https://www.toymoban.com/news/detail-801261.html
到了这里，关于力扣39. 组合总和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
