Almost same solution for two problems Combination Sum and Combination Sum II , C++ Code with comments ,fast


  • 3
    R

    Combination Sum

    code is explained as comments.

    void elementSum(vector<int>&candidates,vector<vector<int>>&res,vector<int>&elements,int target,int start){
                // if the sum of the elements is equal to the target, push this combination into the result
            if(!target){                           
                res.push_back(elements);return;    
            }
            for(int i=start;i<candidates.size();i++){
                   // if current element is bigger than the assigned target, there is 
                   //  no need to keep searching, since all the numbers are positive and sorted
                if(candidates[i]>target) break;
                   //push the valid candidate into the elements vector.
                elements.push_back(candidates[i]);
                   // keep searching for new elements with start as i since here duplicates are allowed
                elementSum(candidates,res,elements,target-candidates[i],i);
                elements.pop_back(); 
            }
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
             vector<vector<int>> res;
             vector<int> elements;
             sort(candidates.begin(),candidates.end());
             elementSum(candidates,res,elements,target,0);
             return res;
        }
    

    Combination Sum II

    void elementSum(vector<int>&candidates,vector<vector<int>>&res,vector<int>&elements,int target,int start){
                 // if the sum of the elements is equal to the target, push this combination into the result
            if(!target){                           
                res.push_back(elements);return;    
            }
            for(int i=start;i<candidates.size();i++){
                 // we always want to count the first element in this recursive step even if it is the same 
                 // as one before. To avoid overcounting, we just ignore the duplicates
                 // after the first element.
                if(i>start && candidates[i]==candidates[i-1]) continue;
                
                  // if current element is bigger than the assigned target, there is 
                  //  no need to keep searching, since all the numbers are positive and sorted
                if(candidates[i]>target) break;
                  //push the valid candidate into the elements vector.
                elements.push_back(candidates[i]);
                  // keep searching for new element with start as i + 1 because one element can be used only once
                elementSum(candidates,res,elements,target-candidates[i],i+1);
                elements.pop_back(); 
            }
        }
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
             vector<vector<int>> res;
             vector<int> elements;
             sort(candidates.begin(),candidates.end());
             elementSum(candidates,res,elements,target,0);
             return res;
        }
    

    Thank you


  • 0
    M

    Amazing its simple and very clear , you just made my day . I have spent hours for this problem and now I found one of the concise solution .


  • 0
    D

    why do we need "elements.pop_back();" ?


Log in to reply
 

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