Simple backtracking code 20ms. With only little change the code also works for problem "Combination Sum II "


  • 0
    I

    class Solution {

    public:

    int backTrack(vector<int> &candidates,vector<int> &path, int pos, int cur){
    	if(cur >= target){
    		if(cur == target)
    			ans.push_back(path);
    		return -1;
    			
    	}
    	int rtn;
    	for(; pos < candidates.size(); pos++){
    		path.push_back(candidates[pos]);
    		//use pos + 1 means Each number in candidates may only be used once in the combination;
    		//rtn = backTrack(candidates, path, pos + 1, cur + candidates[pos]);
    		//use pos means the same repeated number may be chosen from candidates unlimited number of times.
    		rtn = backTrack(candidates, path, pos, cur + candidates[pos]);
    		path.pop_back();
    		if(rtn == -1)
    			return 1;
    		else if(rtn == 1){
    			while(pos < candidates.size() - 1){
    				if(candidates[pos] != candidates[pos + 1])break;
    				pos++;
    			}
    			continue;
    		}
    	}
    	return 1;
    		
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    	sort(candidates.begin(), candidates.end());
    	vector<int>path;
    	this->target = target;
    	backTrack(candidates, path, 0, 0);
    	return ans;
    
    }
    

    private:
    vector<vector<int> >ans;
    int target;
    };


Log in to reply
 

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