**Solution using recursion**:

**Summary**:

The solution is a simple recursion solution, calculating all possible combinations of k based on the result of combinations of k-1.

**Approche #1 Recursion solution**

The function starts from combinations of k numbers and recurivelly call itself for a k reduced by 1: k = k-1.

The base case (the stop condition) is when k equal 0. At this point the function returns a vector containing only one empty vector.

Then at each return iteration we go through all the combinations and for each one of them we create a list of vectors by adding

each new possible number.

When the step for the initial k is reached we add the combination to the final result only if the add up to n condition is verified.

Example:

k = 0 : {{}}

k = 1 : {{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}

k = 2 : {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9},

{2, 3}, {2, 4} .... {2, 9}

{3, 4}, {3, 5} .... {3, 9}

.....

{8, 9}

}

**Complexity analysis**:

**Time complexity**: The algorithm needs to determine all possible combinations of k from 9 (since only numbers from 1 to 9 can be use).

For each combination of k, the total sum of the numbers must also be calculated , which has a complexity of O(k).

So the total time complexity will be O(C(9,k)*k) which is O((9 choose k) * k).

**Space complexity**: O(k * C(9,k))

**C++**

```
class Solution {
private:
int sum(vector<int> iV){
int rsp = 0;
for(auto & i: iV
rsp += i;
}
return rsp;
}
vector<vector<int>> combinationsOfKUpToN(int k, int maxK, int n){
if(k==0){
return vector<vector<int>>{{}};
}
vector<vector<int>> rsp;
for(auto & i: combinationsOfKUpToN(k-1, maxK, n)){
int first = (i.size() > 0) ? i.back()+1 : 1;
for(int nb=first; nb<=9; ++nb){
i.push_back(nb);
if((k != maxK) || ((k == maxK) && (sum(i) == n)) ){
rsp.push_back(i);
}
i.pop_back();
}
}
return rsp;
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
return combinationsOfKUpToN(k, k, n);
}
};
```