Conteo de posibles permutaciones de un número representado como una suma de 2, 4 y 6 solamente

Dado un número entero N , la tarea es encontrar el número de permutaciones en las que N se puede representar como una suma de 2 s, 4 s y 6 s únicamente.
Nota: También se contarán las diferentes permutaciones de una misma combinación.
Ejemplos: 
 

Entrada: N = 8 
Salida: 7 
Explicación: Las combinaciones posibles son: 
2 2 2 2 
4 4 
4 2 2 
2 2 4 
2 4 2 
2 6 
6 2 
Entrada: N = 6 
Salida: 4 
 

Enfoque: para resolver este problema, estamos utilizando un enfoque de programación dinámica : 
 

• Como los posibles números que se pueden sumar para llegar a N son 2, 4 y 6, se pueden considerar como casos base. Al hacer uso de los casos base, se pueden calcular más casos.
• Consideremos una array dp[] de tamaño N + 1 que calcula y almacena en cada índice i las formas posibles de formar un valor i usando solo 2, 4, 6.
•  

dp[2] = 1 
dp[4] = 2 { 4 puede representarse como 2+2, 4} 
dp[6] = 4 { 6 puede representarse como 2+2+2, 2+4, 4+2, 6} 
dp[i] = dp[i-2]+dp[i-4] + dp[i – 6] para todos los valores pares de i en el rango [8, N] 
 

•  
• Por lo tanto, dp[N] contiene la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ code for above implementation
 
#include <bits/stdc++.h>
using namespace std;
 
// Returns number of ways
// to reach score n
int count(int n)
{
    // table[i] will store count
    // of solutions for value i.
    if (n == 2)
        return 1;
    else if (n == 4)
        return 2;
    else if (n == 6)
        return 4;
 
    int table[n + 1], i;
 
    // Initialize all table
    // values as 0
    for (i = 0; i < n + 1; i++)
        table[i] = 0;
 
    // Base case (If given value
    // is 0, 1, 2, or 4)
    table[0] = 0;
    table[2] = 1;
    table[4] = 2;
    table[6] = 4;
 
    for (i = 8; i <= n; i = i + 2) {
 
        table[i] = table[i - 2]
                   + table[i - 4]
                   + table[i - 6];
    }
 
    return table[n];
}
 
// Driver Code
int main(void)
{
    int n = 8;
    cout << count(n);
 
    return 0;
}

// Java code for above implementation
import java.util.*;
class GFG{
 
// Returns number of ways
// to reach score n
static int count(int n)
{
    // table[i] will store count
    // of solutions for value i.
    if (n == 2)
        return 1;
    else if (n == 4)
        return 2;
    else if (n == 6)
        return 4;
 
    int table[] = new int[n + 1];
    int i;
 
    // Initialize all table
    // values as 0
    for (i = 0; i < n + 1; i++)
        table[i] = 0;
 
    // Base case (If given value
    // is 0, 1, 2, or 4)
    table[0] = 0;
    table[2] = 1;
    table[4] = 2;
    table[6] = 4;
 
    for (i = 8; i <= n; i = i + 2)
    {
        table[i] = table[i - 2] +
                   table[i - 4] +
                   table[i - 6];
    }
 
    return table[n];
}
 
// Driver Code
public static void main(String args[])
{
    int n = 8;
    System.out.print(count(n));
}
}
 
// This code is contributed by Akanksha_Rai

# Python3 code for above implementation
 
# Returns number of ways
# to reach score n
def count(n) :
 
    # table[i] will store count
    # of solutions for value i.
    if (n == 2) :
        return 1;
    elif (n == 4) :
        return 2;
    elif (n == 6) :
        return 4;
 
    table = [0] * (n + 1);
 
    # Initialize all table
    # values as 0
    for i in range(n + 1) :
        table[i] = 0;
 
    # Base case (If given value
    # is 0, 1, 2, or 4)
    table[0] = 0;
    table[2] = 1;
    table[4] = 2;
    table[6] = 4;
 
    for i in range(8 , n + 1, 2) :
 
        table[i] = table[i - 2] + \
                   table[i - 4] + \
                   table[i - 6];
 
    return table[n];
 
# Driver Code
if __name__ == "__main__" :
 
    n = 8;
    print(count(n));
 
# This code is contributed by AnkitRai01

// C# code for above implementation
using System;
class GFG{
 
// Returns number of ways
// to reach score n
static int count(int n)
{
    // table[i] will store count
    // of solutions for value i.
    if (n == 2)
        return 1;
    else if (n == 4)
        return 2;
    else if (n == 6)
        return 4;
 
    int []table = new int[n + 1];
    int i;
 
    // Initialize all table
    // values as 0
    for (i = 0; i < n + 1; i++)
        table[i] = 0;
 
    // Base case (If given value
    // is 0, 1, 2, or 4)
    table[0] = 0;
    table[2] = 1;
    table[4] = 2;
    table[6] = 4;
 
    for (i = 8; i <= n; i = i + 2)
    {
        table[i] = table[i - 2] +
                   table[i - 4] +
                   table[i - 6];
    }
 
    return table[n];
}
 
// Driver Code
public static void Main()
{
    int n = 8;
    Console.Write(count(n));
}
}
 
// This code is contributed by Code_Mech

<script>
// Javascript program to implement
// the above approach
 
// Returns number of ways
// to reach score n
function count(n)
{
    // table[i] will store count
    // of solutions for value i.
    if (n == 2)
        return 1;
    else if (n == 4)
        return 2;
    else if (n == 6)
        return 4;
   
    let table = Array.from({length: n+1}, (_, i) => 0);
    let i;
   
    // Initialize all table
    // values as 0
    for (i = 0; i < n + 1; i++)
        table[i] = 0;
   
    // Base case (If given value
    // is 0, 1, 2, or 4)
    table[0] = 0;
    table[2] = 1;
    table[4] = 2;
    table[6] = 4;
   
    for (i = 8; i <= n; i = i + 2)
    {
        table[i] = table[i - 2] +
                   table[i - 4] +
                   table[i - 6];
    }
   
    return table[n];
}
  
  // Driver Code
     
    let n = 8;
    document.write(count(n));
  
 // This code is contributed by susmitakundugoaldanga.
</script>

7

Complejidad temporal: O(N)  
Complejidad espacial auxiliar: O(N)