# C++ solution, using backtracking, 0ms

• ``````class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int> > res;
if(k>9 || k<1 || n>(19-k)*k/2 || n<(k+1)*k/2) return res;
if(k==1){
vector<int> tempVec;
tempVec.push_back(n);
res.push_back(tempVec);
return res;
}

vector<int> val(k,1);
int i=0;
while(val[0]<=n/k){
if(val[i]<10+i+1-k){
i++;
if(i==k-1){
int temp=n-sumVec(val,k-2);
if(temp<10 && temp>val[k-2]){
vector<int> tempVec;
for(int j=0;j<k-1;j++)
tempVec.push_back(val[j]);
tempVec.push_back(temp);
res.push_back(tempVec);
}
i--;
}
val[i]++;
//to avoid the value being larger than the values behind it
int j=i;
while(j<k-1 && val[j]>val[j+1])
{
j++;val[j]=val[i];
}
}
else{
if(i==0) break;
//to avoid missing some cases
for(int j=i;j<k;j++)
val[j]=val[i-1]+1;
i--; val[i]++;
}
}
return res;
}

int sumVec(vector<int> nums,int m){
int sum=0;
for(int i=0;i<=m;i++)
sum+=nums[i];
return sum;
}
};``````

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