Tutorialspoint.dev

Ways to sum to N using array elements with repetition allowed

Given a set of m distinct positive integers and a value ‘N’. The problem is to count the total number of ways we can form ‘N’ by doing sum of the array elements. Repetitions and different arrangements are allowed.

Examples :

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


Approach: The approach 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] 

Below is the implementation of above approach.

C++

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

Output:

Total number of ways = 6

Time Complexity: O(N*m)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

1 Comments

load comments

Subscribe to Our Newsletter