# CSES - Coin Combinations I

Author: Michael Cao

### Prerequisites

Main IdeaExample Code

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:

$dp[w] = \sum_{i=1}^n{(dp[w - coins[i]])}$

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

Any help would be appreciated! Just submit a Pull Request on Github.

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!