all possible distinct non decreasing sequences(combinations) of numbers to reach the given sum with quick performance

Question

I need to count all possible combinations of numbers to reach the given sum. They should be non decreasing(every next number should be greater or equal to previous one). Here is JavaScript code with examples that solves it but it works very long for numbers like 200:

function spreadInteger(N) {
  function generateCombinations(current, remaining, start) {
    if (remaining === 0) {
      console.log(current.join(" ")); // here I can just put counter and remove `current` variable from arguments to make it faster but it is will be still not enough
      return;
    }
    for (let i = start; i <= remaining; i++) {
      generateCombinations([...current, i], remaining - i, i);
    }
  }
  generateCombinations([], N, 1);
}

// spreadInteger(1); // 1 combination
// 1

// spreadInteger(2); // 2 combinations
// 1 1
// 2

// spreadInteger(3); // 3 combinations
// 1 1 1
// 1 2
// 3

// spreadInteger(4); // 5 combinations
// 1 1 1 1
// 1 1 2
// 1 3
// 2 2
// 4

// spreadInteger(5); // 7 combinations
// 1 1 1 1 1
// 1 1 1 2
// 1 1 3
// 1 2 2
// 1 4
// 2 3
// 5

How can I count it faster? I do not need to log all combinations, I just need to count how many such combinations are for a given number N. I do not care about programming language to solve it. I only care about solution, so even pseudo code answer would be accepted. Also assume there is no memory limit if it can speed up computation.

Answer 1

You're looking to count the partitions of an integer n. The mathematical function for doing so is the partition function which has a nice recurrence relation listed on that wiki page:

p(n) = sum((-1^k) * p(n - k*(3*k-1)/2))

The values subtracted from n in each term are the pentagonal numbers which themselves have a nice closed-form expression:

P_n = (3*n^2 - n) / 2

This means you can calculate the number of partitions of an integer n in O(n^1.5) time by building up a table of p(x) values from 1..n incrementally.