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.
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
Brute force
Read full article from 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;
}
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;
}