Given a sum S and number of non-negative number N, how many different ways can N non-negative numbers can be chosen such that their sum is S - I

You are given a number, say 3.  Let us think about different ways 2 non-negative numbers can be added to result in 3.

3 = 3 + 0 = 2 + 1 = 1 + 2 = 0 + 3

There are 4 different ways in which 2 non-negative numbers can be chosen such that the numbers' addition result in 3.

Let us think about different ways 3 non-negative numbers can be added to result in 3.

3
= 0 + 0 + 3
= 0 + 1 + 2
= 0 + 2 + 1
= 0 + 3 + 0
= 1 + 0 + 2
= 1 + 1 + 1
= 1 + 2 + 0
= 2 + 1 + 0
= 2 + 0 + 1
= 3 + 0 + 0

There are 10 different ways in which 3 non-negative numbers can be chosen such that the number's addition result in 3.



Given a sum - S and number of non-negative numbers to choose - N; find the number of ways in which N different non-negative numbers can be chosen such that the sum of the numbers result in S.

How would you solve it?

Bad solution

Find all possible non-negative numbers that would result in S when added.

How can we do that?


Given a Sum S and number N, every possible value for a particular variable will be between (0, S) - both included.

int count_correct_combination(int S, int N) {

int count = 0;

// if only one number needs to be "added", then only S should will be the correct value. So, only one right solution is possible.

if (N == 1) {

return 1;

}

// if Sum is 0, there is only one way for all numbers to be: all zeros

if (S == 0) {

return 1;

}

for (int i = 0; i < S; i++) {

count += count_correct_combination(S-i, N-1)

}

}

How does this work?

Please refer to Partition for more details.

Quick Guide of the algorithm:

| 0 | 1 | 2 | 3 | . | . | . | S |

1. The first number starts from 0 and lets the rest of the numbers to contribute S. Store the number of ways the rest of the numbers can contribute S.
2. Then, the first number takes 1 and lets the rest of the numbers to contribute (S - 1).  Store the number of ways the rest of the numbers can contribute (S - 1).
3. and so on...
4. *Finally*, The first number takes S and lets the rest of the numbers to contribute 0.  Store the number of ways the rest of the numbers can contribute 0.  This will be 1 (because there is only one way N numbers can contribute to 0 - by all being 0 themselves)
5. Add the result of each step above.  That is the result we want.

Complexity

Well, since we are iterating every number for S possible values; for a given S (sum) and N (number of non-negative numbers), we have a worst-case complexity of SN  This is bad.

There is a better solution to this problem.  Let us discuss that in our next post.