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 .
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):
We could not use the coin ci at all β d[s][ci - 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])