DSA sheet / Dynamic programming
Coin Combinations II
Do these first: Coin Combinations I
The problem in brief
Same setup as the previous problem: n distinct coin values (n up to 100), unlimited supply, a target x up to 10^6. But now two ways are the same if they use the same number of each coin, regardless of order. Print the number of distinct ways modulo 10^9 + 7.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1636.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
The previous approach overcounts here: it counts 2 + 3 and 3 + 2 as different. What must you enforce to count them once?
-
Impose a canonical order on the coins: a way is described by how many of coin 1, then how many of coin 2, and so on. Process one coin type at a time.
-
After deciding to allow the first k coin types, how does the count for total s change when you additionally allow coin type k + 1?
-
The update turns out to be a single in-place pass per coin, iterating s upward. Why does upward iteration allow reusing the same coin as often as you like?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The difference between Coin Combinations I and II is entirely in how you enumerate. To count multisets you need a canonical form so each multiset is produced once. The natural one: fix an order on coin types and require the coins of a solution to be used in that order (all the 2s, then all the 3s, then all the 5s). Then a solution is exactly a choice of counts per type.
DP follows: let ways[s] count the multisets that use only the coin types processed so far. When you add a new coin type c, a multiset for total s either uses no c (already counted in ways[s]) or uses at least one c, which is a multiset for s - c over the same enlarged set, plus one more c. So ways[s] += ways[s - c], iterating s upward so that ways[s - c] already includes uses of c. Coin type on the outside, total on the inside is what makes it count unordered combinations.
The habit: to switch from counting sequences to counting sets, change the loop order so that “which item” is decided in a fixed sequence.
Intuition
Hand out coin types one at a time. After you have introduced coin 2, count ways to pay with 2s only; then introduce coin 3 and add the new ways that use 3s; and so on. Nobody ever chooses a 2 after a 3, so no arrangement is double counted.
Approach
- ways[0] = 1, rest 0.
- For each coin c (outer loop), for s from c to x (inner loop, ascending): ways[s] = (ways[s] + ways[s - c]) mod (10^9 + 7).
- Print ways[x].
Pitfalls: the loop nesting is the whole problem, swap it and you get the previous answer; keep sums under the modulus each step; x up to 10^6 and n up to 100 gives 10^8 steps (PyPy for Python).
Complexity
O(n * x) time, O(x) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
scanf("%d %d", &n, &x);
vector<int> coins(n);
for (auto &c : coins) scanf("%d", &c);
const int MOD = 1000000007;
vector<int> ways(x + 1, 0);
ways[0] = 1;
for (int c : coins) {
for (int s = c; s <= x; s++) {
ways[s] += ways[s - c];
if (ways[s] >= MOD) ways[s] -= MOD;
}
}
printf("%d\n", ways[x]);
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
coins = list(map(int, data[2:2 + n]))
MOD = 10**9 + 7
ways = [0] * (x + 1)
ways[0] = 1
for c in coins:
for s in range(c, x + 1):
ways[s] = (ways[s] + ways[s - c]) % MOD
print(ways[x])
main() # heavy at the maximum limits: submit as PyPy 3 on judges that have itimport java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int x = (int) st.nval;
int[] coins = new int[n];
for (int i = 0; i < n; i++) {
st.nextToken();
coins[i] = (int) st.nval;
}
final int MOD = 1_000_000_007;
int[] ways = new int[x + 1];
ways[0] = 1;
for (int c : coins) {
for (int s = c; s <= x; s++) {
ways[s] += ways[s - c];
if (ways[s] >= MOD) ways[s] -= MOD;
}
}
System.out.println(ways[x]);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const x = data[1];
const coins = data.slice(2, 2 + n);
const MOD = 1000000007;
const ways = new Int32Array(x + 1);
ways[0] = 1;
for (const c of coins) {
for (let s = c; s <= x; s++) {
ways[s] += ways[s - c];
if (ways[s] >= MOD) ways[s] -= MOD;
}
}
console.log(ways[x]);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).