回溯
- 思路：
- 定義遞歸函數(shù) dfs(candidates, target, idx)，表示當(dāng)前 candidates 在 idx 位，還剩 target 需要組合；
- 遞歸終止條件：
- target <= 0；
- target == 0 時，將該組合存入結(jié)果數(shù)組；
- candidates 元素已經(jīng)用完，idx = candidates.size()；
- target <= 0；
- 在當(dāng)前函數(shù)中，可以：
- 跳過 candidates[idx] 元素進(jìn)行組合，即 dfs(candidates, target, idx + 1) ；
- 也可以使用?candidates[idx] 元素進(jìn)行組合（因為可以使用重復(fù)元素），即 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;
};文章來源地址http://www.zghlxwxcb.cn/news/detail-801261.html
文章來源：http://www.zghlxwxcb.cn/news/detail-801261.html
到了這里，關(guān)于力扣39. 組合總和的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
