Javascript solution-sharing backtracking algori


  • 0
    C

    subsets solution

    backtrack algori

    /**
     * @param {number[]} nums
     * @return {number[][]}
     * setp 1: elements can only small to large order, so if(i>0) { if(solution[i-1]>solution[i]) { return false; } }
     * setp 2: each element can only be used once, so if(used[i]) { return false; }
     * setp 3: To solve the problem, in the letter cited a certain position, it is necessary to avoid the same letter has been filled. This prevents result in duplicate order.(Forgive me English, use google translate)
     */
    var subsets = function(nums) {
    
    	nums.sort(function(val1, val2){
    		return val1>val2?1:val1<val2?-1:0;
    	})
    	
    	var solution = [];
    	var result = [];
    	var used = [];	// nums, each element can only be used once
    
    	var backTracking = function(k, n) {
    		if(k==n){
    			// console.log(solution);
    			return result.push(solution.slice(0));
    		}else{
    			var last = "";
    			for(var i=0; i<nums.length; ++i){
    				if(used[i]) { continue; }	// when true, express the element(used[i]) has been used
    				if(k>0 && solution[k-1]>nums[i]) { continue; }	// elements can only small to large order
    				if(last==nums[i]) { continue; }	// when nums[i-1] == nums[i], discard(x)
    				used[i] = true;
    				last = nums[i];
    				solution[k] = nums[i];
    				arguments.callee(k+1, n);	// backTracking(k+1, n);
    				used[i] = false;
    			}
    		}
    	};
    
    	for(var i=0; i<=nums.length; ++i){
    		backTracking(0, i);
    		// eg. subsets([2, 1, 2]);
    		// console.log(nums.sort()); [1, 2, 2]
    		// backTracking(0, 0); return [];
    		// backTracking(0, 1); return [1], [2], [2](x);
    		// backTracking(0, 2); return [1, 2], [1, 2](x), [2, 2];
    		// backTracking(0, 3); return [1, 2, 2];
    	}
    
    	return result;
    };
    subsets([2, 1, 2]);
    

Log in to reply
 

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