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
29
| class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ret;
sort(candidates.begin(), candidates.end());
vector<int> temp;
backTrack(ret, candidates, temp, target, 0);
return ret;
}
private:
void backTrack(vector<vector<int>>& ret,vector<int>& candidates, vector<int>& temp, int remain, int start)
{
if(remain < 0)
return;
if(remain == 0)
{
ret.push_back(temp);
return;
}
for(size_t i = start; i < candidates.size(); ++i)
{
temp.push_back(candidates[i]);
backTrack(ret, candidates, temp, remain - candidates[i], i + 1);
temp.pop_back();
while(i+1 < candidates.size() && candidates[i] == candidates[i+1])
++i;
}
}
};
|