Unofficial Editorial (C++)

The key difference between this problem and Coin Combinations I is that we're now trying to find the number of ordered ways to add the coins to $x$. This means that if we had coins $\{1, 3, 5\}$ and $x=4$, adding $1 + 3$ is treated as the same "way" as $3 + 1$.

Solution

We'll let $\texttt{dp}[w]$ equal the number of ordered ways to add the coins up to $w$. In the previous problem, we tried out each coin for each possible $w$. Here, we'll do the reverse, looping through all possible $w$ ($0\leq w \leq x$) for each coin $i$ while updating $\texttt{dp}$ as follows:

This essentially entails switching the order of the nested loops from the previous problem. Since we now loop over the coins before the weights, we only go through the set of coins once, so it's impossible to create two combinations with the same set of coins ordered differently.

Implementation

Time Complexity: $\mathcal{O}(n \cdot x)$

Copy
import sys

MOD = 10**9 + 7

input = sys.stdin.readline  # Faster input. Using normal input() will TLE.

n, x = map(int, input().split())
coins = list(map(int, input().split()))

combinations = [0] * (x + 1)