Number of ways to add up to a sum S with N numbers

There is a closed form formula : binomial(s + n - 1, s) or binomial(s+n-1,n-1)

Those numbers are the simplex numbers.

If you want to compute them, use the log gamma function or arbitrary precision arithmetic.

See https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers

I have my own formula for this. We, together with my friend Gio made an investigative report concerning this. The formula that we got is [2 raised to (n-1) - 1], where n is the number we are looking for how many addends it has.

Let's try.

• If n is 1: its addends are o. There's no two or more numbers that we can add to get a sum of 1 (excluding 0). Let's try a higher number.
• Let's try 4. 4 has addends: 1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 1+3, 2+2, 3+1. Its total is 7. Let's check with the formula. 2 raised to (4-1) - 1 = 2 raised to (3) - 1 = 8-1 =7.
• Let's try 15. 2 raised to (15-1) - 1 = 2 raised to (14) - 1 = 16384 - 1 = 16383. Therefore, there are 16383 ways to add numbers that will equal to 15.

(Note: Addends are positive numbers only.)

(You can try other numbers, to check whether our formula is correct or not.)

Try this recursive function:

f(s, n) = 1                                    if s = 0
        = 0                                    if s != 0 and n = 0
        = sum f(s - i, n - 1) over i in [0, s] otherwise

To use dynamic programming you can cache the value of f after evaluating it, and check if the value already exists in the cache before evaluating it.