[Help] Simple recursive backtracking solution gives TLE.


  • 0
    H
    class Solution {
    public:
        int sum(vector<int> curr)
        {
            int sum=0;
            for(int i=0; i<int(curr.size()); i++)
                sum+=curr[i];
            
            return sum;
        }
    
        bool combinationSumutil(set<vector<int> > &res, vector<int> &curr, vector<int> &candidates, int target)
        {
        	// If sum for the current sequence equals target
            if(sum(curr)==target)
            {
            	sort(curr.begin(), curr.end());
                res.insert(curr);
                //return true;
            }
            
            // Look for each element in candidate set, each time from start
            for(int i=0; i<int(candidates.size()); i++)
            {
                if(sum(curr)+candidates[i]<=target)
                {
                    curr.push_back(candidates[i]);
                    
                    // If current+1 call succeeds, then the current decision is right
                    if(combinationSumutil(res, curr, candidates, target))
                        return true;
                    
                    // Undo current decision, if current+1 call fails
                    curr.pop_back();
                }
            }
            
            // Backtrack if current call fails
            return false;
        }
    
        vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
            set<vector<int> > res;
    
            vector<int> curr;
    
            combinationSumutil(res, curr, candidates, target);
    
            vector<vector<int> > final(res.begin(), res.end());
    
            return final;
        }
    };

Log in to reply
 

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