20 ms concise solution with explanation.


  • 0
    P

    Concise solution. 20 ms solution.
    The algorithms is as follows:

    1. From the start of the array, make two decisions at the same time (recursive calls)
      a) Pick the current position as a part of the possible solution, decrement the counter and recurse.
      b) Move to the next position and start again. (Ignoring the position with which we started)

    Eg. for (2,3,4,5) 5

    In step a pick 2, change the target to 5 -2 and recurse.
    In step b) ignore the first position (decision of not including it at all) and move on.

    These two when recursed cover all possible combinations.

    class Solution {
    public:
       vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
           vector<vector<int>>sumset;
           vector<int> curset;
           //for(auto i = candidates.begin(); i < candidates.end(); ++i)
           sumgame(candidates.begin(), target, candidates, curset, sumset);
           return sumset;
       }
       
       void sumgame(auto i, auto target, auto &candidates, vector<int> &curset, auto &sumset)
       {
    //check for the terminating condition and return if the end of the vector is reached.
           if(i == candidates.end())
               return;
    //recurse while leaving out the current position candidate. This covers half of the branches of the program.
    // Each time the function is called, it makes both decisions at the same time.
           sumgame(i+1, target, candidates, curset, sumset);
    // the following conditions can be shortened at thecost of readability, so not doing it.
           if(target - *i == 0)
           {
               curset.push_back(*i);
               sumset.push_back(curset);
               curset.pop_back();
           }
           if(target - *i > 0)
           {
               curset.push_back(*i);
               sumgame(i, target - *i, candidates, curset, sumset);
               curset.pop_back();
               return;
           }
    
       }
       
    };
    

Log in to reply
 

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