-
Notifications
You must be signed in to change notification settings - Fork 0
/
recursion.js
120 lines (103 loc) · 2.93 KB
/
recursion.js
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 1) Subsets without duplicate (LeetCode)
const subsetsWithDup = function(nums) {
// Define the identifiers required
let result = [];
let n=nums.length;
// Sort nums array
nums.sort((a,b) => a - b);
const findAllSubsets = (idx,n,state) => {
result.push(state.slice());
for(let i=idx; i<n; i++) {
if(i>idx && nums[i] === nums[i-1]) continue;
state.push(nums[i]);
findAllSubsets(i+1, n, state);
state.pop();
}
};
findAllSubsets(0,n,[]);
return result;
};
// Ultra optimized approach
const subsetsWithDup2 = function(nums) {
// Define the identifiers required
let result = [];
let n=nums.length;
nums.sort((a,b) => a - b);
const findAllSubsets = (idx,n,state) => {
result.push(state);
for(let i=idx; i<n; i++) {
if(i>idx && nums[i] === nums[i-1]) continue;
findAllSubsets(i+1, n, [...state, nums[i]]);
}
};
findAllSubsets(0,n,[]);
return result;
};
// 2) Combination Sums
const combinationSum = (candidates, target) => {
// define the identifiers
let result=[];
let n=candidates.length;
const backtracking = (idx, target, state) => {
if(target < 0 || idx === n) {
return;
}
if(target === 0) {
result.push(state);
return;
}
if(target > 0) {
backtracking(idx, target-candidates[idx], [...state, candidates[idx]]);
}
backtracking(idx+1, target, state);
};
backtracking(0, target, []);
return result;
};
// 3) Combination Sum - 2
const combinationSum2 = (candidates, target) => {
// Define the identifiers
let result = [];
let n = candidates.length;
candidates.sort((a,b) => a - b);
function backTracking(idx, target, state){
if(target === 0) {
result.push(state);
return;
}
if(target < 0 || idx === n) return;
for(let i=idx; i<n; i++) {
if(i>idx && candidates[i] === candidates[i-1]) continue;
backTracking(i+1, target - candidates[i], [...state, candidates[i]]);
}
};
backTracking(0, target, []);
return result;
};
combinationSum2([1,2,1,5,6,7,], 8);
// 4) palindrome-partitioning
const partition = (s) => {
// Define the identifiers required
let result = [];
let n=s.length;
const isPalindrome = (s, start, end) => {
while(start <= end) {
if(s[start] !== s[end]) return false;
start++; end--;
}
return true;
}
const findPalindrome = (idx, s, state) => {
if(idx === n) {
result.push(state);
return;
}
for(let i=idx; i<n; i++) {
if(isPalindrome(s, idx, i)) {
findPalindrome(i+1, s, [...state, s.substring(idx,i+1)])
}
}
}
findPalindrome(0,s,[]);
return result;
};