Javascript, solution-sharing, backtracking


  • 0
    C

    Combination Sum II

    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 arr1 = [2, 3, 1]; arr1 = arr1.sort(function(val1, val2) { return val1>val2?1:val1<val2?-1:0; }); arr1 = [1, 2, 3];
     *  step 2: The smallest element of the array. arr1[0];
     *  step 3: target = 3.The maximum length of the returned array. Math.floor(target/arr1[0]) (3/1) 3;
     *  step 4: Writing backtracking algorithm.
     */
        var combinationSum = 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 = [];
        	var result = [];
        	var pushVal = function(solution, n) {
        		var sum = 0;
        		for(var i=0; i<solution.length; ++i){
        			sum += solution[i];
        		}
        		// console.log("solution=["+solution+"]; sum="+sum);
        		return (sum>target)?true:(sum==target&&solution.length==n)?result.push(solution.slice(0)):false;
        	}
        	var backTracking = function(k, n) { // step 4
        		if(k!=n){
        			for(var i=0; i<candidates.length; ++i){
        				if(k>0 && solution[k-1]>candidates[i]) { continue; }	// Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
        				solution[k] = candidates[i];
        				// console.log("candidates["+i+"]="+candidates[i]+";");
        				if(pushVal(solution, n)){ solution.splice(solution.length-1); return true; }
        				arguments.callee(k+1, n);
        				// console.log("candidates["+i+"]="+candidates[i]+";");
        				solution.splice(solution.length-1);
        			}
        		}else{ return false; }
        	}
        	for(var i=1; i<=Math.floor(target/candidates[0]); ++i){ // step 3
        		backTracking(0, i);
        	}
        	return result;
        };
    

Log in to reply
 

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