Combination Sum III


  • 0
    M

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

Log in to reply
 

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