# CSES - Coin Combinations II

Authors: Michael Cao, Nathan Gong, George Pong

### Appears In

SolutionImplementation

Unoffical Editorial (C++)

### Note

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 $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:

$\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.

## Implementation

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

C++

#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

Java

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

Python

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!