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 = [ * len(c) for _ in range(x + 1)]``````
We can start by processing the first coin and update the state `d[s]` for all possible sums of `s` using the first coin. Then move on to the second coin and update all the states `d[s]`. Then to the third one - update `d[s]` 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[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 =  +  * 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: 0.4 seconds

Memory limit: 512 MB

Output limit: 1 MB