# Simple backtracking code 20ms. With only little change the code also works for problem "Combination Sum II "

• class Solution {

public:

``````int backTrack(vector<int> &candidates,vector<int> &path, int pos, int cur){
if(cur >= target){
if(cur == target)
ans.push_back(path);
return -1;

}
int rtn;
for(; pos < candidates.size(); pos++){
path.push_back(candidates[pos]);
//use pos + 1 means Each number in candidates may only be used once in the combination;
//rtn = backTrack(candidates, path, pos + 1, cur + candidates[pos]);
//use pos means the same repeated number may be chosen from candidates unlimited number of times.
rtn = backTrack(candidates, path, pos, cur + candidates[pos]);
path.pop_back();
if(rtn == -1)
return 1;
else if(rtn == 1){
while(pos < candidates.size() - 1){
if(candidates[pos] != candidates[pos + 1])break;
pos++;
}
continue;
}
}
return 1;

}
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int>path;
this->target = target;
backTrack(candidates, path, 0, 0);
return ans;

}
``````

private:
vector<vector<int> >ans;
int target;
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.