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 = 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    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 = 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);     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 = 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 = 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 = 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

 = 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)