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

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

题目概述

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

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

解答

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

Combination Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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

代码在这里

分享到:
Disqus 加载中...

如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理