CSES - Coin Combinations II

Unoffical 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first

Copy
import java.util.*;

public class CoinCombinations2 {
	static final int MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();

		int[] coins = new int[n];

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)