@@ -17,9 +17,10 @@ export default function integerPartition(number) {
1717partitionMatrix [ 0 ] [ numberIndex ] = 0 ;
1818}
1919
20- // Let's fill the first row. It represents the number of way of how we can form
21- // number zero out of numbers 0, 1, 2, ... Obviously there is only one way we could
22- // form number 0 and it is with number 0 itself.
20+ // Let's fill the first column. It represents the number of ways we can form
21+ // number zero out of numbers 0, 0 and 1, 0 and 1 and 2, 0 and 1 and 2 and 3, ...
22+ // Obviously there is only one way we could form number 0
23+ // and it is with number 0 itself.
2324for ( let summandIndex = 0 ; summandIndex <= number ; summandIndex += 1 ) {
2425partitionMatrix [ summandIndex ] [ 0 ] = 1 ;
2526}
@@ -35,7 +36,18 @@ export default function integerPartition(number) {
3536} else {
3637// The number of combinations would equal to number of combinations of forming the same
3738// number but WITHOUT current summand number plus number of combinations of forming the
38- // previous number but WITH current summand.
39+ // <current number - current summand> number but WITH current summand.
40+ // Example: number of ways to form number 4 using summands 1, 2 and 3 is the sum of
41+ // {number of ways to form 4 with sums that begin with 1 +
42+ // number of ways to form 4 with sums that begin with 2 and include 1 } +
43+ // {number of ways to form 4 with sums that begin with 3 and include 2 and 1}
44+ // Taking these sums to proceed in descending order of intergers, this gives us:
45+ // With 1: 1+1+1+1 -> 1 way
46+ // With 2: 2+2, 2+1+1 -> 2 ways
47+ // With 3: 3 + (4-3) <= convince yourself that number of ways to form 4 starting
48+ // with 3 is == number of ways to form 4-3 where 4-3 == <current number-current summand>
49+ // Helper: if there are n ways to get (4-3) then 4 can be represented as 3 + first way,
50+ // 3 + second way, and so on until the 3 + nth way. So answer for 4 is: 1 + 2 + 1 = 4 ways
3951const combosWithoutSummand = partitionMatrix [ summandIndex - 1 ] [ numberIndex ] ;
4052const combosWithSummand = partitionMatrix [ summandIndex ] [ numberIndex - summandIndex ] ;
4153