## Friday, June 24, 2016

### Number of non-negative integral solutions of a + b + c = n - GeeksforGeeks

Number of non-negative integral solutions of a + b + c = n - GeeksforGeeks
Given a number n, find number of ways we can add 3 non-negative integers so that their sum is n.

If we take a closer look at the pattern, we can find that the count of solutions is ((n+1) * (n+2)) / 2. The problem is equivalent to distributing n identical balls in three boxes and the solution is n+1C2. In general, if there are m variables (or boxes), the formula becomes n+m-1Cm-1.
`int` `countIntegralSolutions(``int` `n)`
`{`
`    ``return` `((n+1)*(n+2))/2;`
`}`
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Brute force
`int` `countIntegralSolutions(``int` `n)`
`{`
`    ``// Initialize result`
`    ``int` `result = 0;`

`    ``// Consider all triplets and increment`
`    ``// result whenever sum of a triplet is n.`
`    ``for` `(``int` `i=0; i<=n; i++)`
`      ``for` `(``int` `j=0; j<=n-i; j++)`
`          ``for` `(``int` `k=0; k<=(n-i-j); k++)`
`             ``if` `(i + j + k == n)`
`              ``result++;`

`    ``return` `result;`
`}`
Read full article from Number of non-negative integral solutions of a + b + c = n - GeeksforGeeks