Use the method of summing the elements of the array to N that allow repeating

Given a set of m different positive integers and the value “N”. The problem is to calculate the total number of “N” formed by summing the elements of the array. Duplication and different arrangements are allowed.

Example:

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

Method: This method is based on the concept of dynamic programming.

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]

Here’s an implementation of the above method.

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

The output is as follows:

Total number of ways = 6

Time Complexity: O(N*m)

If you find anything incorrect, or would like to share more information about the above topics, please write a comment.