Accepted C++ Solution Standard Backtracking


  • 3
    R
    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
        	vector<vector<int>> ret;
        	vector<int> partial;
        
        	backTrackingFun(n,k,1,partial,ret);
        	return ret;
        }
        
        void backTrackingFun(int n,int k,int idx,vector<int> partial,vector<vector<int>> &ret){
        	if(1==k){
        		if(idx<=n && n<10){
        			partial.push_back(n);
        			ret.push_back(partial);
        		}
        		return;
        	}
        
        	for(auto i=idx;i<10;++i){
        		if(i<n){
        			partial.push_back(i);
        			backTrackingFun(n-i,k-1,i+1,partial,ret);
        			partial.pop_back();
        		}else{
        			break;
        		}
        	}
        }
    };
    

    well, there is not too much to say.it's not tricky at all.


    combinationSum2 and combinationSum below.
    content of the caller function is the same only backTrackingFun is different.

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    	vector<vector<int>> ret;
    	vector<int> partial;
    	sort(candidates.begin(),candidates.end());
    	backTrackingFun(candidates,target,0,partial,ret);
    
    	return ret;
    }
    

    combinationSum2

    void backTrackingFun(const vector<int>& candidates, int target,int idx,vector<int> partial,vector<vector<int>> &ret){
    	if(0==target){
    		ret.push_back(partial);
    		return;
    	}
    
    	int size=candidates.size();
    	for(auto i=idx;i<size;++i){
    		int v=candidates[i];
    		// remove dups
    		if(i>idx && v==candidates[i-1]) continue;
    
    		if(v<=target){
    			partial.push_back(v);
    			backTrackingFun(candidates,target-v,i+1,partial,ret);
    			partial.pop_back();
    		}else{
    			break;
    		}
    	}
    }
    

    combinationSum

    void backTrackingFun(const vector<int>& candidates, int target,int idx,vector<int> partial,vector<vector<int>> &ret){
    	if(0==target){
    		ret.push_back(partial);
    		return;
    	}
    
    	int size=candidates.size();
    	for(auto i=idx;i<size;++i){
    		int v=candidates.at(i);
    		if(v<=target){
    			partial.push_back(v);
    			backTrackingFun(candidates,target-v,i,partial,ret);
    			partial.pop_back();
    		}else{
    			break;
    		}
    	}
    }

Log in to reply
 

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