Accepted 9ms C++ solution, easy understand


  • 0
    T
    class Solution {
    public:
        void helper(vector<int>& nums,int target, int end, vector<int> &seq, vector<vector<int> >& ans){
            if(target==0) {
                ans.push_back(seq);
                return;
            }
            if(0>end) return;
            if(target<nums[0]) return;
            while(nums[end]>target&&end>0) end--;
            for(int i=end;i>=0;i--){
                int j=i;
                seq.push_back(nums[i]);
                while(nums[j]>target-nums[i]&&j>0) j--;
                helper(nums,target-nums[i],i,seq,ans);
                seq.pop_back();
            }
        }
        
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sort(candidates.begin(),candidates.end());
            vector<vector<int> > ans;
            vector<int>seq;
            helper(candidates,target,(int)candidates.size()-1,seq,ans);
            return ans;
        }
    };
    

Log in to reply
 

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