17

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?

Hari Sundararajan
  • 608
  • 2
  • 8
  • 18
  • 1
    duplicate (on math.stackexchange): http://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers – Alexandre C. Jan 03 '11 at 21:20
  • The dynamic programming solution is not too different from that of the classic [0-1 knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem). The differences are that we're only interested in full knapsacks (trivial change to the solution) and those containing exactly N items (minor change to the solution). – moinudin Jan 03 '11 at 21:22

6 Answers6

9

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.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 1
    Caching is memoization, not DP. – moinudin Jan 03 '11 at 21:26
  • 21
    @marcog: Caching is an example of dynamic programming. It's called top-down dynamic programming. Search for "memoize" here: http://en.wikipedia.org/wiki/Dynamic_programming – Mark Byers Jan 03 '11 at 21:29
  • 1
    Don't cite wikipedia. :) The two are related, but memoization is not DP. – moinudin Jan 03 '11 at 21:34
  • 3
    @marcog, when memoization is used to cache the solutions to subproblems in order to solve bigger problems, as it is here, it fits exactly into the definition of dynamic programming. Although yes, in general, caching solutions is not equal to dynamic programming. – mdenton8 May 09 '16 at 00:53
  • Couldn't understand your code @MarkByers. Can you please clarify a bit – Soumalya Bhattacharya Mar 25 '22 at 14:38
6

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

Josh Vander Hook
  • 256
  • 1
  • 13
Alexandre C.
  • 55,948
  • 11
  • 128
  • 197
  • I didn't see the proof in that link. The relationship binomial(s+n-1, *s*) seems to match expectations. For example, for s=5, n=2, we have binomial (5+2-1,2) --> binomial(6,2)=15, when I'd expect 6 (0,5; 1,4; 2,3; 3,2; 4,1; 5,0), which is binomial(n+s-1,s), or alternatively binomial(n+s-1,n-1). Perhaps I misunderstand, but I couldn't verify from the proof in your link. – Josh Vander Hook Jul 02 '20 at 16:55
5

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

Thomas Kingston
  • 115
  • 1
  • 8
Marvin Mercado
  • 51
  • 1
  • 1
  • This is helpful but I think the question was about adding to 4 with x numbers. So only 1,2,1 would be a solution for x = 3 – user3475234 Apr 15 '16 at 16:59
3

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

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • What if you don't have all the range [0..s] to choose from? What if you also have a and b and all the numbers used in sums have to come from [a..b]? for S = 5 and N = 3 and a = 1 and b = 4, the results will be <1,1,3> <1,2,2> <1,3,1> <2,1,2> <2,2,1> and <3,1,1> with the total of 6.. Is there a formula for that? – Andrew Savinykh Jun 09 '15 at 11:50
1

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)

user2107425
  • 11
  • 1
0

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.

nycdan
  • 2,819
  • 2
  • 21
  • 33