Algorithms and Data Structures

Coin change - the number of ways

Given a money system that consists of n coins, each coin has a positive value . You are asked to find the number of ways to obtain a total amount of x by using the coins.
For instance, if the coin values are and we need to obtain 5, there are 4 different ways to do that: 5, 1 + 2 + 2, 1 + 1 + 1 + 2, and 1 + 1 + 1 + 1 + 1. Unlike the combination sum, here the order doesn’t matter - we’re only interested in the multiset of coins that we use.

Input

The first line of the input contains two integers n (1 ≤ n ≤ 100) and x (1 ≤ x ≤ ).
The next line contains n space-separated integers (1 ≤ ≤ ).

Output

The program should print the number of ways possible to obtain x using the given coins. As the answer can get very large, you are asked to print it modulo .

Examples

Input
Output
3 5 1 2 5
4
3 9 2 3 5
3

Explanation

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, and 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Tutorial

Notice that if we store a state with d[s] where d[s] is the number of different ways to obtain the sum s by using the coins, we will have an issue of double counting where we would count the same set of coins several times. So, for the set of 1 + 2 + 2 (which should be counted only once), we would have it counted 3 times for all their combinations: 1 + 2 + 2, 2 + 1 + 2, and 2 + 2 + 1.
To address this issue, we would count the number of ways to obtain the value s by processing all the coins up to ci (ci is the index of the coin in the array c). We are allowed to not use ci at all or use it multiple times - all of that is captured in the state. So, our state d[s][ci] would represent the number of ways to obtain the sum s by processing all the coins up to ci.
 
There are 2 transitions that can get us from some of the previous states to the current d[s][ci] (the index of the current coin is ci and its value is val):
  1. We could not use the coin ci at all → d[s][ci - 1]
  1. We could use the coin ci for 0, 1, 2, … k times → d[s - val][ci]
So, the total number of ways to obtain the sum s with all the coins up to ci would be the sum of all the transitions from the previous states described above.
 
c = [...]
x = ...
# Initialize d with x+1 rows and len(c) columns of 0s
d = [[0] * len(c) for _ in range(x + 1)]
We can start by processing the first coin and update the state d[s][0] for all possible sums of s using the first coin. Then move on to the second coin and update all the states d[s][1]. Then to the third one - update d[s][2] and so on up until reaching the last coin.
After processing all the coins, we can print the number of possible ways to reach the sum x by printing the state of reaching x after processing the last coin - d[x][len(c) - 1]:
for ci, val in enumerate(c):      # Iterate over coins one-by-one
    d[0][ci] = 1                  # Possible to obtain sum of 0 with no coins
    for s in range(1, x + 1):     # Iterate over all the sums 1...x inclusive
        if ci - 1 >= 0:           # (1) Not use ci at all
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) Use ci for 0+ times
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 Can you think of a way to keep a one-dimensional list for d?
We process the coins one by one, so, it’s possible to throw away all the computed states for the coin ci - 2 and before. On each iteration, we’re only interested in the current coin ci and the previous coin ci - 1. So, we can keep the previous coin’s state in one array and the current coin’s state in another.
😎 Can you think of a way to not use any auxiliary array and only use a 1-dimensional d?
We can notice that the only operation from the previous coin’s state is the addition of prev[s] to d[s]. So, we can omit keeping the previous array at all:
# Initialize d x+1 items
d = [1] + [0] * x                 # Possible to obtain sum of 0 with no coins

for ci, val in enumerate(c):      # Iterate over coins one-by-one
    for s in range(1, x + 1):     # Iterate over all the sums 1...x inclusive
        if s - val >= 0:          # (2) Use ci for 0+ times
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in