Maneras de sumar a N usando elementos de array con repetición permitida

Dado un conjunto de m enteros positivos distintos y un valor ‘N’. El problema es contar el número total de formas en que podemos formar ‘N’ haciendo la suma de los elementos del arreglo. Se permiten repeticiones y arreglos diferentes.

Ejemplos: 

Input : arr = {1, 5, 6}, N = 7
Output : 6

Explanation:- The different ways are:
1+1+1+1+1+1+1
1+1+5
1+5+1
5+1+1
1+6
6+1

Input : arr = {12, 3, 1, 9}, N = 14
Output : 150

Enfoque: El enfoque se basa en el concepto de programación dinámica. 

countWays(arr, m, N)
        Declare and initialize count[N + 1] = {0}
        count[0] = 1
        for i = 1 to N
            for j = 0 to m - 1
                if i >= arr[j]
                   count[i] += count[i - arr[j]]
        return count[N] 

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

C++

// C++ implementation to count ways
// to sum up to a given value N
#include <bits/stdc++.h>
 
using namespace std;
 
// function to count the total
// number of ways to sum up to 'N'
int countWays(int arr[], int m, int N)
{
    int count[N + 1];
    memset(count, 0, sizeof(count));
     
    // base case
    count[0] = 1;
     
    // count ways for all values up
    // to 'N' and store the result
    for (int i = 1; i <= N; i++)
        for (int j = 0; j < m; j++)
 
            // if i >= arr[j] then
            // accumulate count for value 'i' as
            // ways to form value 'i-arr[j]'
            if (i >= arr[j])
                count[i] += count[i - arr[j]];
     
    // required number of ways
    return count[N];
     
}
 
// Driver code
int main()
{
    int arr[] = {1, 5, 6};
    int m = sizeof(arr) / sizeof(arr[0]);
    int N = 7;
    cout << "Total number of ways = "
        << countWays(arr, m, N);
    return 0;
}

Java

// Java implementation to count ways 
// to sum up to a given value N
 
class Gfg
{
    static int arr[] = {1, 5, 6};
     
    // method to count the total number
    // of ways to sum up to 'N'
    static int countWays(int N)
    {
        int count[] = new int[N + 1];
         
        // base case
        count[0] = 1;
         
        // count ways for all values up
        // to 'N' and store the result
        for (int i = 1; i <= N; i++)
            for (int j = 0; j < arr.length; j++)
     
                // if i >= arr[j] then
                // accumulate count for value 'i' as
                // ways to form value 'i-arr[j]'
                if (i >= arr[j])
                    count[i] += count[i - arr[j]];
         
        // required number of ways
        return count[N];
         
    }
     
    // Driver code
    public static void main(String[] args)
    {
        int N = 7;
        System.out.println("Total number of ways = "
                                    + countWays(N));
    }
}

Python3

# Python3 implementation to count
# ways to sum up to a given value N
 
# Function to count the total
# number of ways to sum up to 'N'
def countWays(arr, m, N):
 
    count = [0 for i in range(N + 1)]
     
    # base case
    count[0] = 1
     
    # Count ways for all values up
    # to 'N' and store the result
    for i in range(1, N + 1):
        for j in range(m):
 
            # if i >= arr[j] then
            # accumulate count for value 'i' as
            # ways to form value 'i-arr[j]'
            if (i >= arr[j]):
                count[i] += count[i - arr[j]]
     
    # required number of ways
    return count[N]
     
# Driver Code
arr = [1, 5, 6]
m = len(arr)
N = 7
print("Total number of ways = ",
           countWays(arr, m, N))
            
# This code is contributed by Anant Agarwal.

C#

// C# implementation to count ways 
// to sum up to a given value N
using System;
 
class Gfg
{
    static int []arr = {1, 5, 6};
     
    // method to count the total number
    // of ways to sum up to 'N'
    static int countWays(int N)
    {
        int []count = new int[N+1];
         
        // base case
        count[0] = 1;
         
        // count ways for all values up
        // to 'N' and store the result
        for (int i = 1; i <= N; i++)
            for (int j = 0; j < arr.Length; j++)
     
                // if i >= arr[j] then
                // accumulate count for value 'i' as
                // ways to form value 'i-arr[j]'
                if (i >= arr[j])
                    count[i] += count[i - arr[j]];
         
        // required number of ways
        return count[N];
         
    }
     
    // Driver code
    public static void Main()
    {
        int N = 7;
        Console.Write("Total number of ways = "
                                    + countWays(N));
    }
}
 
//This code is contributed by nitin mittal.

PHP

<?php
// PHP implementation to count ways
// to sum up to a given value N
 
// function to count the total
// number of ways to sum up to 'N'
function countWays($arr, $m, $N)
{
    $count = array_fill(0,$N + 1,0);
     
    // base case
    $count[0] = 1;
     
    // count ways for all values up
    // to 'N' and store the result
    for ($i = 1; $i <= $N; $i++)
        for ($j = 0; $j < $m; $j++)
 
            // if i >= arr[j] then
            // accumulate count for value 'i' as
            // ways to form value 'i-arr[j]'
            if ($i >= $arr[$j])
                $count[$i] += $count[$i - $arr[$j]];
     
    // required number of ways
    return $count[$N];
     
}
 
// Driver code
$arr = array(1, 5, 6);
$m =  count($arr);
$N = 7;
echo "Total number of ways = ",countWays($arr, $m, $N);
 
// This code is contributed by Ryuga
?>

Javascript

<script>
 
    // JavaScript implementation to count ways 
    // to sum up to a given value N
     
    let arr = [1, 5, 6];
       
    // method to count the total number
    // of ways to sum up to 'N'
    function countWays(N)
    {
        let count = new Array(N+1);
        count.fill(0);
           
        // base case
        count[0] = 1;
           
        // count ways for all values up
        // to 'N' and store the result
        for (let i = 1; i <= N; i++)
            for (let j = 0; j < arr.length; j++)
       
                // if i >= arr[j] then
                // accumulate count for value 'i' as
                // ways to form value 'i-arr[j]'
                if (i >= arr[j])
                    count[i] += count[i - arr[j]];
           
        // required number of ways
        return count[N];
           
    }
     
    let N = 7;
      document.write("Total number of ways = " + countWays(N));
     
</script>
Producción

Total number of ways = 6

Complejidad de tiempo: O(N*m)

Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *