1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | class Solution {
public:
void dfs(int idx, int size, int sum, int target,
vector<int>& cur,
vector<int>& candidates,
vector<vector<int>>& ans) {
if (sum > target)
return;
if (sum == target) {
ans.push_back(cur);
return;
}
if (idx >= candidates.size())
return;
cur.push_back(candidates[idx]);
dfs(idx, size + 1, sum + candidates[idx], target, cur, candidates, ans);
cur.pop_back();
dfs(idx + 1, size, sum, target, cur, candidates, ans);
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
std::vector<int> cur;
dfs(0, 0, 0, target, cur, candidates, ans);
return ans;
}
};
|