CODEWITHSUNDEEP
calgorithm
lakshmen
lakshmen

Reputation: 29064

Finding the number of different combinations of numbers such that its total equals to sum

I would like to find out the number of different combinations of non-negative numbers(can be any number, it is not fixed) such that its total equals to the sum that is provided.

for example : I have 3 numbers and i want to find the different combinations of numbers such that the sum is 4. the value of num starts from 0. no negative numbers.

For 3 numbers that sum to 4, the combinations are 

2 0 2
2 2 0
0 2 2
0 1 3
3 1 0
0 3 1 
1 0 3
1 3 0
3 0 1
0 0 4
4 0 0
0 4 0
2 1 1
1 2 1
1 1 2

I saw this as an example : Finding the total number combinations for an integer using three numbers

But the problem is it only uses three numbers.

Any algorithm or code will be useful. Thanks.

Upvotes: 0

Views: 1567

Answers (2)

sch
sch

Reputation: 27506

You can view this as the number of ways to put s indistinguishable coins in n distinguishable jars. (In the example, s=4 and n=3).

As explained here, that is C(n+s-1,s-1), which gives 15 in the example.

Upvotes: 5

Luka Rahne
Luka Rahne

Reputation: 10447

If order does not matter and 0 counts too, like in example link, then

n=total+1
k=number-1
binomial(k+n-1,k)  #combinations whith reptetitions
or
binomial(number+total-1,number-1)

If you represent number 5 as 

 1+1+1+1+1

and have to find number of sums sums whith 3 integers
You can see that you have to do 2 slices out of 6 calculating combinations whit repetitions.

Upvotes: 3

Related Questions