# Accepted C++ Solution Standard Backtracking

• ``````class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ret;
vector<int> partial;

backTrackingFun(n,k,1,partial,ret);
return ret;
}

void backTrackingFun(int n,int k,int idx,vector<int> partial,vector<vector<int>> &ret){
if(1==k){
if(idx<=n && n<10){
partial.push_back(n);
ret.push_back(partial);
}
return;
}

for(auto i=idx;i<10;++i){
if(i<n){
partial.push_back(i);
backTrackingFun(n-i,k-1,i+1,partial,ret);
partial.pop_back();
}else{
break;
}
}
}
};
``````

well, there is not too much to say.it's not tricky at all.

combinationSum2 and combinationSum below.
content of the caller function is the same only backTrackingFun is different.

``````vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> partial;
sort(candidates.begin(),candidates.end());
backTrackingFun(candidates,target,0,partial,ret);

return ret;
}
``````

combinationSum2

``````void backTrackingFun(const vector<int>& candidates, int target,int idx,vector<int> partial,vector<vector<int>> &ret){
if(0==target){
ret.push_back(partial);
return;
}

int size=candidates.size();
for(auto i=idx;i<size;++i){
int v=candidates[i];
// remove dups
if(i>idx && v==candidates[i-1]) continue;

if(v<=target){
partial.push_back(v);
backTrackingFun(candidates,target-v,i+1,partial,ret);
partial.pop_back();
}else{
break;
}
}
}
``````

combinationSum

``````void backTrackingFun(const vector<int>& candidates, int target,int idx,vector<int> partial,vector<vector<int>> &ret){
if(0==target){
ret.push_back(partial);
return;
}

int size=candidates.size();
for(auto i=idx;i<size;++i){
int v=candidates.at(i);
if(v<=target){
partial.push_back(v);
backTrackingFun(candidates,target-v,i,partial,ret);
partial.pop_back();
}else{
break;
}
}
}``````

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