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