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

Given a number n, find number of ways we can add 3 non-negative integers so that their sum is n.

Examples :

```Input : n = 1
Output : 3
There are four ways to get sum 1.
(1, 0, 0), (0, 1, 0) and (0, 0, 1)

Input : n = 2
Output : 6
There are six ways to get sum 2.
(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0)
(1, 0, 1) and (0, 1, 1)

Input : n = 3
Output : 10
There are ten ways to get sum 10.
(3, 0, 0), (0, 3, 0), (0, 0, 3), (1, 2, 0)
(1, 0, 2), (0, 1, 2), (2, 1, 0), (2, 0, 1),
(0, 2, 1) and (1, 1, 1)
```

Method 1 [ Brute Force : O(n3) ]
A simple solutions is to consider all triplets using three loops. For every triplet, check if its sum is equal to n. If sum is n, increment count of solutions.

Below is the implementation.

## C++

 `// A naive C++ solution to count solutions of ` `// a + b + c = n ` `#include ` `using` `namespace` `std; ` ` `  `// Returns count of solutions of a + b + c = n ` `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; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 3; ` `    ``cout <<  countIntegralSolutions(n); ` `    ``return` `0; ` `} `

## Java

 `// A naive Java solution to count ` `// solutions of a + b + c = n ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``// Returns count of solutions of a + b + c = n ` `    ``static` `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; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `n = ``3``; ` `        ``System.out.println( countIntegralSolutions(n)); ` `     `  `    ``} ` `} ` ` `  `// This article is contributed by vt_m `

/div>

## Python3

 `# Python3 code to count  ` `# solutions of a + b + c = n ` ` `  `# Returns count of solutions ` `# of a + b + c = n ` `def` `countIntegralSolutions (n): ` ` `  `    ``# Initialize result ` `    ``result ``=` `0` `     `  `    ``# Consider all triplets and  ` `    ``# increment result whenever  ` `    ``# sum of a triplet is n. ` `    ``for` `i ``in` `range``(n ``+` `1``): ` `        ``for` `j ``in` `range``(n ``+` `1``): ` `            ``for` `k ``in` `range``(n ``+` `1``): ` `                ``if` `i ``+` `j ``+` `k ``=``=` `n: ` `                    ``result ``+``=` `1` `     `  `    ``return` `result ` `     `  `# Driver code ` `n ``=` `3` `print``(countIntegralSolutions(n)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

## C#

 `// A naive C# solution to count ` `// solutions of a + b + c = n ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns count of solutions ` `    ``// of a + b + c = n ` `    ``static` `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; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `n = 3; ` `        ``Console.Write(countIntegralSolutions(n)); ` `     `  `    ``} ` `} ` ` `  `// This article is contributed by Smitha. `

## PHP

 ` `

Output :

`10`

Method 2 [ Direct Formula : O(1) ]
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 + 1 identical balls (for 0 to n) in three boxes and the solution is n+2C2. In general, if there are m variables (or boxes) and n possible values, the formula becomes n+m-1Cm-1.

## C++

 `// A naive C++ solution to count solutions of ` `// a + b + c = n ` `#include ` `using` `namespace` `std; ` ` `  `// Returns count of solutions of a + b + c = n ` `int` `countIntegralSolutions(``int` `n) ` `{ ` `    ``return` `((n+1)*(n+2))/2; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 3; ` `    ``cout <<  countIntegralSolutions(n); ` `    ``return` `0; ` `}`

## Java

 `// Java solution to count  ` `// solutions of a + b + c = n ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``// Returns count of solutions  ` `    ``// of a + b + c = n ` `    ``static` `int` `countIntegralSolutions(``int` `n) ` `    ``{ ` `    ``return` `((n + ``1``) * (n + ``2``)) / ``2``; ` `         `  `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `n = ``3``; ` `        ``System.out.println ( countIntegralSolutions(n)); ` `         `  `    ``} ` `} ` `// This article is contributed by vt_m `

## Python3

 `# Python3 solution to count  ` `# solutions of a + b + c = n ` ` `  `# Returns count of solutions ` `# of a + b + c = n ` `def` `countIntegralSolutions (n): ` `    ``return` `int``(((n ``+` `1``) ``*` `(n ``+` `2``)) ``/` `2``) ` `     `  `# Driver code ` `n ``=` `3` `print``(countIntegralSolutions(n)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

## C#

 `// C# solution to count  ` `// solutions of a + b + c = n ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns count of solutions  ` `    ``// of a + b + c = n ` `    ``static` `int` `countIntegralSolutions(``int` `n) ` `    ``{ ` `        ``return` `((n + 1) * (n + 2)) / 2; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main (String[] args)  ` `    ``{ ` `        ``int` `n = 3; ` `        ``Console.Write ( countIntegralSolutions(n)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by parashar. `

## PHP

 ` `

Output :

`10`