Javascript, solution-sharing, backtracking


  • 0
    C

    Combination Sum

    If you still do not quite understand, it is recommended to see this article. backtracking algorithm

    Of course, this is just my algorithm, there are many better better solution.

    /**
     *  English is poor, use google translate.
     *  step 1: array sort; // var candidates= [10,1,2,7,6,1,5].; candidates=candidates.sort(function(val1, val2) { return val1>val2?1:val1<val2?-1:0; }); candidates= [1,1,2,5,6,7,10];
     *  step 2: Each number in C may only be used once in the combination. 
     *  step 3: Since Step 2, The maximum length of the returned array is candidates.length;
     *  step 4: Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
     *  step 5: Writing backtracking algorithm.
     */
    var combinationSum2 = function(candidates, target) {
    	candidates = candidates.sort(function(val1, val2) { // step 1
    		return val1>val2?1:val1<val2?-1:0;
    	});
    	// console.log("candidates=["+candidates+"];");
    	var	solution = [], result = [], used = []; // used = []; step 2
    	var pushVal = function(solution, n) {
    		for(var sum=0,i=0; i<solution.length; ++i){
    			sum += solution[i];
    		}
    		// console.log("solution=["+solution+"]; sum="+sum);
    		return sum<target?false:(sum==target&&solution.length==n)?result.push(solution.slice(0)):true;
    		// return (sum>target)?true:(sum==target&&solution.length==n)?result.push(solution.slice(0)):false;
    	}
    	var backTracking = function(k, n) { // step 5
    		if(k!=n){
    			var last_num = ""; // candidates= [1,1,2,5,6,7,10]; target=8; A:[candidates[0]=1,candidates[1]=1,candidates[4]=6], B:[candidates[1]=1,candidates[0]=1,candidates[4]=6], A=B. A,B only one, need.
    			for(var i=0; i<candidates.length; ++i){
    				if(k>0 && solution[k-1]>candidates[i]) { continue; }	// step 4
    				if(used[i]) { continue; }
    				if(last_num ==candidates[i]) { continue; }
    				used[i] = true;
    				last_num = candidates[i];
    				solution[k] = candidates[i];
    				// console.log("candidates["+i+"]="+candidates[i]+"; used["+i+"]="+used[i]+";");
    				if(pushVal(solution, n)){ used[i]=false; solution.splice(solution.length-1); return true; }
    				arguments.callee(k+1, n);
    				used[i] = false;
    				// console.log("candidates["+i+"]="+candidates[i]+"; used["+i+"]="+used[i]+";");
    				solution.splice(solution.length-1);
    			}
    		}else{ return false; }
    	}
    	for(var i=1; i<=candidates.length; ++i){ // step 3
    		backTracking(0, i);
    	}
    	return result;
    };
    combinationSum2([10,1,2,7,6,1,5], 8);
    

Log in to reply
 

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