# Elegant C++ 0ms solution with recursive DFS

• ``````class Solution {
public:

static void dfs(vector<int> & current, vector<vector<int>> & result, const int k, int left){
if(left <= 0) return;
int numLeft = k - current.size();   //Num of numbers to be inserted into the "current" array
int minSum, maxSum;     //The min(max) possible sum of numbers to add to the "current" array

if(current.empty()){    //Corner situations: uninitialized "current" array
minSum = (k * (1 + numLeft)) >> 1; //Gauss sum formula
maxSum = ((19 - k) * k) >> 1;
}
else{
minSum = numLeft * (((current.back() << 1) + 1 + numLeft) >> 1);
maxSum = ((19 - numLeft) * numLeft) >> 1;
}

if(left < minSum || left > maxSum) return;  //No solutions will be found
else if(numLeft == 1){     //A possible solution is found
current.push_back(left);
result.push_back(current);
current.pop_back();
}
else{
for(int i = current.empty() ? 1 : (current.back() + 1); i < 10; ++i){
current.push_back(i);
dfs(current, result, k, left - i);
current.pop_back();
}
}
}

vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
if(k == 0 || n == 0) return result;
vector<int> current;
dfs(current, result, k, n);
return result;
}

};``````

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