CSES - Coin Combinations II

Authors: Michael Cao, Nathan Gong, George Pong

Table of Contents


Unoffical Editorial (C++)


The solution for this problem is very similar to that of Coin Combinations I. If you haven't solved that already, we recommend doing so before attempting this problem.

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 xx. This means that if we had coins {1,3,5}\{1, 3, 5\} and x=4x=4, adding 1+31 + 3 is treated as the same "way" as 3+13 + 1.


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

dp[w]:=dp[w]+dp[wcoins[i]]\texttt{dp}[w] := \texttt{dp}[w] + \texttt{dp}[w-\texttt{coins}[i]]

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.


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


#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


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];


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)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!