LeetCode39,40,46,47,78,90-Backtracking

这是对标题所列几道题目的一个总结。分别是：

题目概述

我相信你能看懂题目！简单说一下。

Combination Sum就是给定一个数组和目标值，求解在给定数组中，和为目标值的组成方式有多少种？（元素是否能被重复使用）
Permutations就是给定一个数组，求解元素的排列方式有多少种？（给定数组中是否有重复元素）
Subsets就是给定一个数组，求解一共有多少个子集？（给定数组中是否有重复元素）

解答

六道题都有一个共同的思路，那就是使用Backtracking来求解，或说是递归、回溯。

Combination Sum

// Runtime: 76 ms, faster than 97.05% of JavaScript online submissions.
// Memory Usage: 36.6 MB, less than 47.76% of JavaScript online submissions.
var combinationSum = function(candidates, target) {
    candidates=candidates.sort((a,b) => {
        return a-b;
    });
    let tempRtn=[],rtn=[];
    solve(candidates,0,target,tempRtn,rtn);
    return rtn;
};
var solve = function(arr,index,target,tempRtn,rtn){
    if(target < 0){
        return;
    }
    if(target === 0){
        //Array.from
        rtn.push(Array.from(tempRtn));
        return;
    }
    for(let i=index;i<arr.length;i++){
        if(i>index && arr[i]===arr[i-1]){
            continue;
        }
        tempRtn.push(arr[i]);
        solve(arr,i,target-arr[i],tempRtn,rtn);
        solve(arr,i+1,target-arr[i],tempRtn,rtn);//each item just can be used once
        tempRtn.pop();
    }
}

Combination Sum II

// Runtime: 72 ms, faster than 99.86% of JavaScript online submissions.
// Memory Usage: 36.5 MB, less than 59.26% of JavaScript online submissions.
var combinationSum2 = function(candidates, target) {
    candidates=candidates.sort((a,b) => {
        return a-b;
    });
    let tempRtn=[],rtn=[];
    solve(candidates,0,target,tempRtn,rtn);
    return rtn;
};
var solve = function(arr,index,target,tempRtn,rtn){
    if(target < 0){
        return;
    }
    if(target === 0){
        rtn.push(Array.from(tempRtn));
        return;
    }
    for(let i=index;i<arr.length;i++){
        if(i>index && arr[i]===arr[i-1]){
            continue;
        }
        tempRtn.push(arr[i]);
        solve(arr,i+1,target-arr[i],tempRtn,rtn);
        tempRtn.pop();
    }
}

Permutations

// Runtime: 72 ms, faster than 53.55% of JavaScript online submissions.
// Memory Usage: 37.4 MB, less than 19.11% of JavaScript online submissions.
var permute = function(nums) {
    if(nums.length===0){
        return [[]];
    }
    let rtn=[],tempRtn=[];
    permutation(nums,tempRtn,rtn);
    return rtn;
};
var permutation = function(arr,temp,rtn){
    let len=arr.length;
    if(len===1){
        temp.push(arr[0]);
        rtn.push(Array.from(temp));
        temp.pop();
        return;
    }
    for(let i=0;i<len;i++){
        temp.push(arr[i]);
        let tempNums=arr.slice(0);
        tempNums.splice(i,1);
        permutation(tempNums,temp,rtn);
        temp.pop();
    }
}

Permutations II

// Runtime: 84 ms, faster than 49.36% of JavaScript online submissions.
// Memory Usage: 37.2 MB, less than 89.22% of JavaScript online submissions.
var permuteUnique = function(nums) {
    if(nums.length===0){
        return [[]];
    }
    nums=nums.sort((a,b) => {
        return a-b;
    })
    let rtn=[],tempRtn=[];
    permutation(nums,tempRtn,rtn);
    return rtn;
};
var permutation = function(arr,temp,rtn){
    let len=arr.length;
    if(len===1){
        temp.push(arr[0]);
        rtn.push(Array.from(temp));
        temp.pop();
        return;
    }
    for(let i=0;i<len;i++){
        if(i>0 && arr[i]==arr[i-1]){
            continue;
        }
        temp.push(arr[i]);
        let tempNums=arr.slice(0);
        tempNums.splice(i,1);
        permutation(tempNums,temp,rtn);
        temp.pop();
    }
}

Subsets

// solution 1
// Runtime: 56 ms, faster than 94.08% of JavaScript online submissions.
// Memory Usage: 35.3 MB, less than 38.76% of JavaScript online submissions.
var subsets = function(nums) {
    let rtn = [], tempRtn = [];
    recur(tempRtn,rtn,nums,0);
    return rtn;
};
var recur = function(tempRtn,rtn,arr,s){
    rtn.push(Array.from(tempRtn));
    for(let i=s;i<arr.length;i++){
        tempRtn.push(arr[i]);
        recur(tempRtn,rtn,arr,i+1);
        tempRtn.pop();
    }
}
// solution 2
// Runtime: 68 ms, faster than 26.94% of JavaScript online submissions.
// Memory Usage: 36.2 MB, less than 9.07% of JavaScript online submissions.
var subsets = function(nums) {
    let len = nums.length, rtn = [], tempRtn = [];
    rtn.push([]);
    if(len == 0){
        return rtn;
    }
    rtn.push(nums);
    for(let i=1;i<=Math.floor(len/2);i++){
        recur(tempRtn,rtn,nums,0,len,i);
    }
    let hash = {}, final = [];
    for(let i = 0, len2 = rtn.length; i < len2; i++){  
        if(!hash[rtn[i]]){  
            final.push(rtn[i]);  
            hash[rtn[i]] = true;  
        }  
    }  
    return final;
};
var recur = function(tempRtn,rtn,array,s,r,k){
    if(k == 0){
        let remain = array.filter((item) => {
            return tempRtn.indexOf(item) == -1
        })
        rtn.push(Array.from(tempRtn));
        rtn.push(remain);
        return;
    }
    for(let i=s;i<r;i++){
        tempRtn.push(array[i]);
        recur(tempRtn,rtn,array,i+1,r,k-1);
        tempRtn.pop();
    }
}

Subsets II

// Runtime: 60 ms, faster than 90.04% of JavaScript online submissions.
// Memory Usage: 36.4 MB, less than 50.32% of JavaScript online submissions.
var subsetsWithDup = function(nums) {
    nums = nums.sort((a,b) => {
        return a-b;
    })
    let rtn = [], tempRtn = [];
    recur(tempRtn,rtn,nums,0);
    return rtn;
};
var recur = function(tempRtn,rtn,nums,s){
    rtn.push(Array.from(tempRtn));
    for(let i=s;i<nums.length;i++){
        if(i>s && nums[i]==nums[i-1]) continue;
        tempRtn.push(nums[i]);
        recur(tempRtn,rtn,nums,i+1);
        tempRtn.pop();
    }
}

Code

代码在这里