How Do I Solve This Complex Javascript Algorithm Without Overcomplicating it?

Question

How many ways can you make the sum of a number?

From wikipedia: https://en.wikipedia.org/wiki/Partition_(number_theory)#

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
Examples
Basic
sum(1) // 1
sum(2) // 2  -> 1+1 , 2
sum(3) // 3 -> 1+1+1, 1+2, 3
sum(4) // 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
sum(5) // 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3

sum(10) // 42
Explosive
sum(50) // 204226
sum(80) // 15796476
sum(100) // 190569292

My Attempt

I tried to loop through two arrays simultaneously and test them against eachother. This doesn't work (at least in the way I did it) for a few reasons.

My Code:

function sum(num, arr = []) {
  if(num == 0){
    return testNumbers(arr, num);
}
  arr.push(num);
  return sum(num - 1, arr);


function testNumbers(arrr, n){
  let arr2 = [...arrr];
  let count = 0; 

  let calculations = arrr.filter((item)=>{
  return item + arr2.map((a)=>{
     return a;
   }) == n;
    
  })


console.log(calculations);

}


}


console.log(sum(10));

You don't need to fix my code, as I don't think its salvageable, but how do you solve the problem?

Answer 1

This is in fact a fairly simple recursion, if we think of the problem as counting the partitions with a given lower bound. We have two simple bases cases of 0 and 1 if the lower bound is greater than our target number or equal to it. Otherwise we recur in two ways, one for when we use that lower bound, and one for when we don't. Here's one version, where lb is the lower bound of the numbers to use:

const count = (n, lb = 1) =>
  lb > n
    ? 0
  : lb == n
    ? 1
  : count (n - lb, lb) + count (n, lb + 1)

This counts the number of partitions with the given lower bound. So count(10, 3) would yield 5, one for each array in [[3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]. Although the default value for the lower bound means that we can call it with just our target number, there are potential issues with this if we tried, say, to map over it. So it might be best to wrap this in a separate function, const countPartitions = (n) => count (n, 1)

const count = (n, lb) =>
  lb > n
    ? 0
  : lb == n
    ? 1
  : count (n - lb, lb) + count (n, lb + 1)

const countPartitions = (n) => count (n, 1)

console .log ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10] .map (countPartitions))

But this will be quite slow for larger input. My test for 100 took 56.3 seconds.) If we memoize the intermediate results, we should speed things up a great deal. We can do this manually or, as I'd prefer, with a memoization helper:

const memoize = (makeKey, fn) => {
  const memo = {}
  return (...args) => {
    const key = makeKey (...args)
    return memo [key] || (memo [key] = fn (...args))
  }
}

const count = memoize (
  (n, lb) => `${n}~${lb}`, 
  (n, lb) => 
    lb > n
      ? 0
    : lb == n
      ? 1
    : count (n - lb, lb) + count (n, lb + 1)
)

const countPartitions = (n) => count (n, 1)

console .log (countPartitions (100))

And this now takes 20 milliseconds in my test.

Answer 2

We can get a speed up over Scott's solution by using the recurrence relation for the partition function that uses pentagonal numbers:

function _p(k, memo){
  if (k == 0)
    return 1;

  if (memo[k])
    return memo[k];

  let result = 0;
  let i = 1;
  const ms = [1, 1, -1, -1];
  
  while (true){
    const n = i & 1 ? (i + 1) / 2 : -i / 2;
    const pentagonal = (3*n*n - n) / 2;

    if (pentagonal > k)
      break;

    result = result + ms[(i-1) % 4] * _p(k - pentagonal, memo);
    i = i + 1;
  }
  
  return memo[k] = result;
}

function p(k){
  return _p(k, {});
}

var ks = [1, 2, 3, 4, 5, 6, 10, 50, 80, 100];
for (let k of ks){
  const start = new Date;
  console.log(`${ k }: ${ p(k) }`);
  console.log(`${ new Date - start } ms`);
  console.log('');
}