0ms C++ recursive backtracking


  • 0
    C

    vector<int>soFar saved the temporary result. Push matched soFar with correct steps k to vector<vector<int>> ret.

     class Solution {
        public:
           void sum3Recur(int k, int target, int start, vector<int>& soFar, vector<vector<int>>& ret)
           {
              if (k==0)
              {
                 if (target == 0)
                 {
                    ret.push_back(soFar);
                 }
              }
              else
              {
                 for (int i = start; i< 10 && i<= target; i++)
                 {
                    soFar.push_back(i);
                    sum3Recur(k-1, target-i, i+1, soFar, ret);
                    soFar.pop_back();
                 }
              }
           }
        
           vector<vector<int>> combinationSum3(int k, int n) 
           {
              vector<vector<int>> ret;
              vector<int> soFar;
        
              sum3Recur(k, n, 1, soFar, ret);
        
              return ret;
           }
        };

Log in to reply
 

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