My recursive 16ms cpp code


  • 0
    C
    class Solution {
    public:
        vector< vector<int> > result;
        
        void helper(vector<int> &candidates, int candidate_id, vector<int> &res, int target)
        {
            if(target < 0) return;
            
            if(!target && res.size() > 0)
            {
                result.push_back( vector<int>(res) );
                return;
            }
            
            if(candidate_id >= candidates.size()) return;
            if(candidates[candidate_id] > target) return;
            
            if(candidate_id == candidates.size()-1 && (target % candidates.back() == 0))
            {
                int tmp = target / candidates.back();
                
                result.push_back( vector<int>(res) );
                auto sol = result.end() - 1;
                
                for(int i=0; i < tmp; i++)
                    sol->push_back( candidates.back() );
                    
                return;
            }
            
            // choose candidates[candidate_id]
            res.push_back(candidates[candidate_id]);
            helper(candidates, candidate_id, res, target - candidates[candidate_id]);
            res.pop_back();
            
            // not choose candidates[candidate_id]
            helper(candidates, candidate_id+1, res, target);
        }
        
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
        {
            std::sort(candidates.begin(), candidates.end());
            
            vector<int> res;
            
            helper(candidates, 0, res, target);
            
            return result;
        }
    };

Log in to reply
 

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