39. 组合总和 - 力扣(LeetCode) (leetcode-cn.com)
组合总和
- DFS
- 回溯
- 剪枝
- 遇到可以重复取数怎么办?
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void DFS(vector<int>& candidates, int target, int sum, int index) {
//剪枝
if (sum > target) return;
if (sum == target) {
ans.emplace_back(path);
return;
}
for (int i = index; i < candidates.size(); ++i) {
sum += candidates[i];
path.emplace_back(candidates[i]);
// 遇到可以重复取数怎么办?
// 我们重新取i,即可。不可以重复取数就i+1跳过重复。
DFS(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
DFS(candidates, target, 0, 0);
return ans;
}
};