# 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 ` ` `  `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

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