Coin Mix Count
Medium1-D Dynamic Programming
Problem
You have an unlimited number of coins of each value in coins (all distinct). A mix is a multiset of coins: how many of each value you use, regardless of order.
Return the number of different mixes whose total is exactly amount, modulo 1,000,000,007.
Example 1
- Input:
- amount = 5, coins = [1, 2, 5]
- Output:
- 4
5; 2+2+1; 2+1+1+1; 1+1+1+1+1.
Example 2
- Input:
- amount = 3, coins = [2]
- Output:
- 0
Example 3
- Input:
- amount = 0, coins = [3, 4]
- Output:
- 1
The empty mix.
Constraints
- 0 ≤ amount ≤ 5000
- 1 ≤ coins.length ≤ 300
- 1 ≤ coins[i] ≤ 5000, all distinct
Hint
Show the first hint
If you count 'last coin used' the way you would for ordered sequences, 1+2 and 2+1 are both counted. How do you force one canonical order?
Walkthrough
How to approach it
01Clarify before coding
- Is 1+2 the same mix as 2+1? Yes: order does not matter.
- What about amount = 0? There is exactly one mix, the empty one.
- Why the modulo? The count explodes for large amounts with many small coins.
02Brute force
Recurse over coin index i and remaining amount: use c[i] zero, one, two … times, then move to i + 1. Memoising on (i, remaining) gives an O(k·amount) table with a 2-D state.
Cost: Without memo it is exponential. The memoised 2-D version is O(k·amount) time and O(k·amount) space, which the 1-D trick below cuts to O(amount).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.