Javascript solution backtracking


  • 0
    C
    // forgive me English
    // setp 1: length=k all possible Combination
    // setp 2: find length=k all possible Combination, sum = n
    var combinationSum3 = function(k, n) {
    	var solution = [];	// length=k all possible Combination
    	var result = [];
    	var used = [];	// [1,2,...,9] each element can only be used once
    
    	var backTracking = function(m, n) {
    		if(m==k){
    			var sum = 0;
    			for(var i=0; i<solution.length; ++i){
    				sum += solution[i];
    			}
    			if(sum==n){
    				console.log(solution);	// print out all possible
    				result.push(solution.slice(0));
    			}
    		}else{
    			for(var i=1; i<=9; ++i){
    				if(used[i]){ continue; }	// when true, express the element(used[i]) has been used
    				if(m>0 && solution[m-1]>i){ continue; }	// elements can only small to large order
    				used[i] = true;
    				solution[m] = i;
    				arguments.callee(m+1, n);
    				used[i] = false;
    			}
    		}
    	}
    
    	backTracking(0, n);
    
    	return result;
    };

Log in to reply
 

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