# Combination Sum III

• 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);
}
};
``````

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