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;}