Accepted code of my solution(12 ms C++)


  • 0
    J
    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>> result;
    		vector<int> path;
    		sort(candidates.begin(),candidates.end());
    		dfs(result,candidates,path,0,target);
    		return result;
        }
    private:
    	void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
    		if(!path.empty()&&target==0){
    			result.push_back(path);
    			return;
    		}
    		if(current<candidates.size()){
    			int tmp = -1;//start from 0 and 1
    			for(;current<candidates.size();current++){
    				
    				if(candidates[current]==tmp)
    					continue;
    				if(target-candidates[current]<0)
    					return;
    
    				tmp = candidates[current];
    				path.push_back(candidates[current]);
    				dfs(result,candidates,path,current+1,target-candidates[current]);
    				path.pop_back();
    			}
    		}
    	}
    };

Log in to reply
 

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