# Dynamic Programming Python implementation of Coin

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins. The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Input:

The first line contains an integer 'T' denoting the total number of test cases. In each test cases, the first line contains an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, ..., AN denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

Output:

Print number of possible ways to make change for N cents.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 300
1 1 ≤ A[i] ≤ 300

Example:

Input:

2
3
1 2 3
4
4
2 5 3 6
10

Output:

4
5

** For More Input/Output Examples Use 'Expected Output' option **

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):

# table[i] will be storing the number of solutions for
# value i. We need n+1 rows as the table is constructed
# in bottom up manner using the base case (n = 0)
# Initialize all table values as 0
table = [0 for k in range(n+1)]

# Base case (If given value is 0)
table[0] = 1

# Pick all coins one by one and update the table[] values
# after the index greater than or equal to the value of the
# picked coin
for i in range(0,m):
for j in range(S[i],n+1):
table[j] += table[j-S[i]]

return table[n]

# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
x = count(arr, m, n)
print (x)

# This code is contributed by Afzal Ansari

4
>>>