39 组合总和II
class Solution {
private:
vector<int> res;
vector<vector<int>> ans;
void dfs(const vector<int>& candidates, vector<int>& res, int target,
int index) {
if (index == candidates.size()) {
return;
}
if (target == 0) {
ans.push_back(res);
return;
}
// 不选这个数
dfs(candidates, res, target, index + 1);
// 选这个数
if (candidates[index] <= target) {
res.push_back(candidates[index]);
dfs(candidates, res, target - candidates[index], index);
res.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, res, target, 0);
return ans;
}
};