Número de soluciones integrales no negativas de a + b + c = n

Dado un número n, encuentre el número de formas en que podemos sumar 3 enteros no negativos para que su suma sea n.
Ejemplos: 
 

Input : n = 1
Output : 3
There are three 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 3.
(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)

Método 1 [Fuerza bruta: O(n ³ )] 
Una solución simple es considerar todos los tripletes usando tres bucles. Para cada triplete, compruebe si su suma es igual a n. Si la suma es n, incrementa el conteo de soluciones. 
A continuación se muestra la implementación. 
 

// A naive C++ solution to count solutions of
// a + b + c = n
#include<bits/stdc++.h>
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;
}

// 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

# 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".

// 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
// A naive PHP solution
// to count solutions of
// a + b + c = n
 
// Returns count of
// solutions of a + b + c = n
function countIntegralSolutions( $n)
{
     
    // Initialize result
    $result = 0;
 
    // Consider all triplets and increment
    // result whenever sum of a triplet is n.
    for ($i = 0; $i <= $n; $i++)
        for ($j = 0; $j <= $n - $i; $j++)
            for ($k = 0; $k <= ($n - $i - $j); $k++)
            if ($i + $j + $k == $n)
            $result++;
 
    return $result;
}
 
    // Driver Code
    $n = 3;
    echo countIntegralSolutions($n);
 
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program solution to count
// solutions of a + b + c = n
 
  // Returns count of solutions of a + b + c = n
    function countIntegralSolutions(n)
    {
        // Initialize result
        let result = 0;
       
        // Consider all triplets and increment
        // result whenever sum of a triplet is n.
        for (let i = 0; i <= n; i++)
        for (let j = 0; j <= n - i; j++)
            for (let k = 0; k <= (n - i - j); k++)
                if (i + j + k == n)
                result++;
       
        return result;
    }
 
// Driver Code
 
    let n = 3;
    document.write(countIntegralSolutions(n));
 
</script>

Producción: 

10

Complejidad temporal: O(n ³ )

Espacio Auxiliar: O(1)

Método 2 [Fórmula directa: O(1)] 
Si observamos más de cerca el patrón, podemos encontrar que el recuento de soluciones es ((n+1) * (n+2)) / 2. El problema es equivalente a repartir n bolas idénticas en tres cajas y la solución es ⁿ⁺² C ₂ . En general, si hay m variables (o cajas) y n bolas, la fórmula se convierte en ^n+m-1 C _m-1 . 
 

// A naive C++ solution to count solutions of
// a + b + c = n
#include<bits/stdc++.h>
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 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 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# 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
// A naive PHP solution
// to count solutions of
// a + b + c = n
 
// Returns count of solutions
// of a + b + c = n
function countIntegralSolutions($n)
{
    return (($n + 1) * ($n + 2)) / 2;
}
 
    // Driver Code
    $n = 3;
    echo countIntegralSolutions($n);
 
// This code is contributed by anuj_67.
?>

<script>
 
// A naive JavaScript solution
// to count solutions of
// a + b + c = n
 
// Returns count of solutions of a + b + c = n
function countIntegralSolutions(n)
{
    return Math.floor(((n+1)*(n+2))/2);
}
 
// Driver code
 
    let n = 3;
    document.write(countIntegralSolutions(n));
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción : 

10

Complejidad del tiempo: O(1)

Espacio auxiliar: O(1)
Este artículo es una contribución de Shivam Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.