Elegant C++ 0ms solution with recursive DFS


  • 0
    J
    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;
        }
        
    };

Log in to reply
 

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