-
Notifications
You must be signed in to change notification settings - Fork 0
/
HowSum.js
61 lines (56 loc) · 1.59 KB
/
HowSum.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
//m= target sum
//n= array length
//Recursion
/*const howSum =(targetsum, numbers) => { // T.C. = O(n^m*m) S.C. = O(m)
if(targetsum===0) return [];
if(targetsum<0) return null;
let remainder;
let ret;
for(let num of numbers) {
//console.log(num);
remainder=targetsum-num;
ret=howSum(remainder, numbers)
if(ret!=null)
return [...ret,num];
}
return null;
}*/
//Memoization
/*const howSum =(targetsum, numbers,memo = {}) => { // T.C. = O(n*m^2) S.C. = O(m^2)
if(targetsum in memo) return memo[targetsum];
if(targetsum===0) return [];
if(targetsum<0) return null;
let remainder;
let ret;
for(let num of numbers) {
//console.log(num);
remainder=targetsum-num;
ret=howSum(remainder, numbers,memo)
if(ret!=null) {
memo[targetsum]=[...ret,num];
return memo[targetsum];
}
}
memo[targetsum]= null;
return null;
}*/
//Tabulation
const howSum = (targetsum, numbers) => { // T.C. = O(n*m^2) S.C. = O(m^2)
const table = Array(targetsum+1).fill(null);
table[0]=[];
// console.log(table);
for(let i=0;i<=targetsum;i++) {
if(table[i]!=null) {
for(let num of numbers) {
if(i+num<=targetsum)
table[i+num]=[num, ...table[i]];
}
}
}
return table[targetsum];
}
console.log(howSum(7,[2,3]));//[ 3, 2, 2 ]
console.log(howSum(7,[2,4]));//null
console.log(howSum(7,[2,5,3,7]));//[ 3, 2, 2 ]
console.log(howSum(8,[3,2,5]));//[ 2, 3, 3 ]
console.log(howSum(300,[7,14]));//null