Javascript solution-sharing backtracking


  • 0
    C

    subsets II solution

    backtrack algori

    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    var subsets = function(nums) {
    	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{
    			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
    				used[i] = true;
    				solution[k] = nums[i];
    				arguments.callee(k+1, n);
    				used[i] = false;
    			}
    		}
    	}
    
    	for(var i=0; i<=nums.length; ++i){
    		backTracking(0, i);
    		// eg. subsets([1, 2, 3]);
    		// backTracking(0, 0); return [];
    		// backTracking(0, 1); return [1], [2], [3];
    		// backTracking(0, 2); return [1, 2], [1, 3], [2, 3];
    		// backTracking(0, 3); return [1, 2, 3];
    	}
    
    	return result;
    };
    subsets([1, 2, 3]);
    

  • 0
    W

    public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
    List<Integer> sub = new ArrayList<Integer>();
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Arrays.sort(nums);
    combination(nums, result, sub, 0);
    return result;
    }
    public void combination(int[] nums, List<List<Integer>> result, List<Integer> sub, int start){
    result.add(new ArrayList(sub));
    for(int i = start; i < nums.length; i++){
    if(i > start && nums[i] == nums[i-1]){
    continue;
    }
    sub.add(nums[i]);
    combination(nums, result, sub, i+1);
    sub.remove(sub.size() - 1);
    }
    return;
    }
    }

    my easy and consise java conclusion with recursion and backtarcking


Log in to reply
 

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