forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
integerPartition.js
57 lines (51 loc) · 2.59 KB
/
integerPartition.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
/**
* @param {number} number
* @return {number}
*/
export default function integerPartition(number) {
// Create partition matrix for solving this task using Dynamic Programming.
const partitionMatrix = Array(number + 1).fill(null).map(() => {
return Array(number + 1).fill(null);
});
// Fill partition matrix with initial values.
// Let's fill the first row that represents how many ways we would have
// to combine the numbers 1, 2, 3, ..., n with number 0. We would have zero
// ways obviously since with zero number we may form only zero.
for (let numberIndex = 1; numberIndex <= number; numberIndex += 1) {
partitionMatrix[0][numberIndex] = 0;
}
// Let's fill the first column. It represents the number of ways we can form
// number zero out of numbers 0, 0 and 1, 0 and 1 and 2, 0 and 1 and 2 and 3, ...
// Obviously there is only one way we could form number 0
// and it is with number 0 itself.
for (let summandIndex = 0; summandIndex <= number; summandIndex += 1) {
partitionMatrix[summandIndex][0] = 1;
}
// Now let's go through other possible options of how we could form number m out of
// summands 0, 1, ..., m using Dynamic Programming approach.
for (let summandIndex = 1; summandIndex <= number; summandIndex += 1) {
for (let numberIndex = 1; numberIndex <= number; numberIndex += 1) {
if (summandIndex > numberIndex) {
// If summand number is bigger then current number itself then just it won't add
// any new ways of forming the number. Thus we may just copy the number from row above.
partitionMatrix[summandIndex][numberIndex] = partitionMatrix[summandIndex - 1][numberIndex];
} else {
/*
* The number of combinations would equal to number of combinations of forming the same
* number but WITHOUT current summand number PLUS number of combinations of forming the
* <current number - current summand> number but WITH current summand.
*
* Example:
* Number of ways to form 5 using summands {0, 1, 2} would equal the SUM of:
* - number of ways to form 5 using summands {0, 1} (we've excluded summand 2)
* - number of ways to form 3 (because 5 - 2 = 3) using summands {0, 1, 2}
* (we've included summand 2)
*/
const combosWithoutSummand = partitionMatrix[summandIndex - 1][numberIndex];
const combosWithSummand = partitionMatrix[summandIndex][numberIndex - summandIndex];
partitionMatrix[summandIndex][numberIndex] = combosWithoutSummand + combosWithSummand;
}
}
}
return partitionMatrix[number][number];
}