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 - II

Please refer to previous post for more information regarding the problem that we are discussing.

In our previous post, we discussed a bad solution for the problem of finding how many combination of N non-negative numbers can we find such that it yields a given sum S.

The complexity of the discussed solution was SN 

The solution had a sample Java code for the method - count_correct_combination

Let us again consider S = 3 and N = 3.  To compute this answer, we compute

S = 3, N = 3

S = 3, N = 2

S = 3, N = 1

S = 2, N = 1

S = 1, N = 1

S = 2, N = 2

S = 2, N = 1

S = 1, N = 1

S = 1, N = 2

S = 1, N = 1

S = 0, N = 2

We can find that S = 1, N = 1 is calculated repeatedly.  For some large input values of N and S, there will be many such intermediate values of S and N that will get calculated repeatedly.  All these contributes to exponential complexity.

This can be improved by remembering what the value was when we calculated the result for a give S and N.

To do that, create a two-dimensional array of dimensions (S + 1, N) and store intermediate values in the array.  S + 1 - because there are S + 1 possible values for every variable (0 to S - both included).

Variables\Sum	0	1	2	.	.	S - 1	S
Number             1	1	1	1	1	1	1	1
of                  2	1
variables          .	1
.	1
N - 1	1
N	1

The first column and the first row are all 1's.  This is because of the following two facts:

1. The number of different ways we can choose N non-negative numbers such that the sum of the numbers is 0 = is always 1.  This is because to get sum(n numbers) = 0, we need every number to be equal to 0.  There is no other way to pick non-negative numbers to result in sum of zero.
2. The number of different ways in which 1 variable can result in a sum of S = is 1.  That is that one variable should be = S.  Otherwise, sum(variables) will not be = S.

To calculate the value for the rest of the elements in our array, we know that result of (S, N) = sum of (S - x, N - 1) where x = 0 to S (both included).  Applying this formula 

Variables\Sum	0	1	2	.	.	S - 1	S
Number             1	1	1	1	1	1	1	1
of                   2	1					xxx	= value(0, 1) + value(1, 1).. + value(S, 1)
variables          .	1					xxx
.	1					xxx
N - 1	1	xxx	xxxx	xxx	xxx	xxx	= value(0, N-2) + value(1, N-2).. + value(S, N-2)
N	1	= value(0, N-1) + value(1, N-1)				= value(0, N-1) + value(1, N-1).. + value(S-1, N-1)	= value(0, N-1) + value(1, N-1).. + value(S, N-1)

In other words, the value of any element in a given (col, row) is equal to sum of values of all elements from 0th column till col in the row above.

But if we do a sum of elements in a row-above to find values in the desired row, we might be computing sum of first few elements again and again.  This can be simplified further.

So, given col1 and row1 for which we need to calculate value, we do 

value(col1,row1) = (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1))

To find the value of col1 + 1, row1, we do (Note: Take note of how the paranthesis changes)

= (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1) + value(col1 + 1, row1 - 1))

=  (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1)) + value(col1 + 1, row1 - 1)

= value(col1,row1) + value(col1 + 1, row1 - 1)

Translating this to an arbitrary col, row, we get:

value(col, row) = value(col - 1, row) + value(col, row - 1)

In simple words, value of an element at col1, row1 = value of cell above + value of cell to the left.



The revised code for our new logic:

int count_correct_combination(int S, int N) {

int count = 0; 

int[][] sumArray = new int[S+1][N];

for (int iDx = 0; iDx < S + 1; iDx++) { 

for (int jDx = 0; jDx < N; jDx ++) {

if (iDx == 0 || jDx == 0) {

 sumArray[iDx][jDx] = 1;

} else { 

   sumArray[iDx][jDx] = sumArray[iDx-1][jDx] + sumArray[iDx][jDx - 1];

} 

} 

 return sumArray[S][N - 1];

} 

This reduces the complexity to find the result to (S*N) - way better than SN that we achieved before.