# CSES - Coin Combinations I

Author: Michael Cao

In this problem, we are asked the number of ways to achieve some value, $x$, using $n$ coins of distinct values where the order of coins does not matter. This is known as the "Unordered Coin Change" problem, which you can read about in CPH Chapter 7 under "Counting the Number of Solutions".

# Main Idea

To solve this problem, let $\texttt{dp[w]}$ equal the number of ways to achieve the sum of values, $w$. Then, for some weight $w$, let's try to use each coin. For $\texttt{dp[w]}$, we'll transition from $\texttt{dp[w - coin[i]]}$ for all $i$, where $\texttt{coin[x]}$ defines the value of the $x$-th coin.

So, the transitions are:

### Warning!

Remember to take your answer mod $10^9 + 7$, as instructed in the problem statement.

## Example Code

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

### Note

An otherwise working solution that uses `dp[i] %= m;`

instead of
`if (dp[i] > M) dp[i] -= M;`

may time out on CSES, but would work on USACO,
which gives double time for Java (see line 32 of the solution).

import java.io.*;import java.util.*;public class CountingCoins1 {static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(System.out);public static void main(String[] args) throws IOException {StringTokenizer st = new StringTokenizer(r.readLine());int n = Integer.parseInt(st.nextToken());

Python

### This section is not complete.

We don't currently have a Python solution for this problem. Please switch to another language to view the solution code.

### 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!