-
Notifications
You must be signed in to change notification settings - Fork 0
/
CombinationSumII.cpp
31 lines (31 loc) · 1004 Bytes
/
CombinationSumII.cpp
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
30
31
class Solution {
public:
vector<vector<int>> ans;
void find(vector<int> &vi,set<vector<int>> &s,vector<int>& candidates,vector<int>& v, int target,int i=0){
if(target==0){
if(s.find(v)==s.end()){
ans.push_back(v);
s.insert(v);
}
return;
}
for(int j=i;j<candidates.size() and target>=candidates[j];j++){
if(vi[j]==0){
v.push_back(candidates[j]);
vi[j]=1;
find(vi,s,candidates,v,target-candidates[j],j);
vi[j]=0;
v.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<int> v;
vector<int> vi(candidates.size());
//for(int i=0;i<candidates.size();i++) vi.push_back(1);
set<vector<int>> s;
find(vi,s,candidates,v,target);
return ans;
}
};