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

问题:

Say S = 5 and N = 3 the solutions would look like - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> <2,3,0> <3,2,0> <1,2,2> etc etc.

In the general case, N nested loops can be used to solve the problem. Run N nested loop, inside them check if the loop variables add upto S.

If we do not know N ahead of time, we can use a recursive solution. In each level, run a loop starting from 0 to N, and then call the function itself again. When we reach a depth of N, see if the numbers obtained add up to S.

Any other dynamic programming solution?

回答1:

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.

回答2:

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

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

回答3:

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.)

回答4:

This can be calculated in O(s+n) (or O(1) if you don't mind an approximation) in the following way:

Imagine we have a string with n-1 X's in it and s o's. So for your example of s=5, n=3, one example string would be

oXooXoo

Notice that the X's divide the o's into three distinct groupings: one of length 1, length 2, and length 2. This corresponds to your solution of <1,2,2>. Every possible string gives us a different solution, by counting the number of o's in a row (a 0 is possible: for example, XoooooX would correspond to <0,5,0>). So by counting the number of possible strings of this form, we get the answer to your question.

There are s+(n-1) positions to choose for s o's, so the answer is Choose(s+n-1, s).

回答5:

This actually looks a lot like a Towers of Hanoi problem, without the constraint of stacking disks only on larger disks. You have S disks that can be in any combination on N towers. So that's what got me thinking about it.

What I suspect is that there is a formula we can deduce that doesn't require the recursive programming. I'll need a bit more time though.

回答6:

There is a fixed formula to find the answer. If you want to find the number of ways to get N as the sum of R elements. The answer is always: (N+R-1)!/((R-1)!*(N)!) or in other words: (N+R-1) C (R-1)