Simple 20 ms C++ Solution


  • 0
    R
    class Solution {
    public:
        void combinationSumUtil(vector<int> &candidates, int target, vector< vector<int> >& dv, vector<int> &v,  int sum, int index) {
            int i;
            int len = candidates.size();
            
            if(sum == target) {
                dv.push_back(v);
                return;
            }
            if(sum > target)
                return;
            
            for(i=index; i<len; i++) {
                if(sum+candidates[i] <= target) {
                    v.push_back(candidates[i]);
                    combinationSumUtil(candidates, target, dv, v, sum+candidates[i], i);
                    v.pop_back();
                }
            }
        }
    
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector< vector<int> > dv;
            vector<int> v;
            int sum = 0, index = 0;
            
            sort(candidates.begin(), candidates.end()); 
    
            /* Index: from where the for loop to run  */
            combinationSumUtil(candidates, target, dv, v, sum, index);
            return dv;
        }
    };

Log in to reply
 

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