Ways to Pay the Exact Fare
Medium2-D Dynamic Programming
Problem
A ticket machine accepts coins of the distinct denominations in coins, and you have an unlimited supply of each. The fare is amount.
Return the number of different combinations of coins that add up to exactly amount. The order in which coins are inserted does not matter: 2 + 5 and 5 + 2 are the same combination.
Example 1
- Input:
- amount = 7, coins = [2, 3, 5]
- Output:
- 2
2 + 5 and 2 + 2 + 3.
Example 2
- Input:
- amount = 4, coins = [3]
- Output:
- 0
Example 3
- Input:
- amount = 0, coins = [4, 9]
- Output:
- 1
Paying nothing is one combination: the empty one.
Constraints
- 0 ≤ amount ≤ 5000
- 1 ≤ coins.length ≤ 300
- 1 ≤ coins[i] ≤ 5000, all distinct
- The answer fits in a signed 32-bit integer.
Hint
Show the first hint
Counting orderings and counting combinations are different. How can you make sure each combination is counted once?
Walkthrough
How to approach it
01Clarify before coding
- Does order matter? No, 2 + 5 and 5 + 2 are the same combination.
- Is the supply unlimited? Yes, any number of each coin.
- What if amount is 0? There is exactly one combination, the empty one.
02Brute force
Recursively choose a count for each denomination in turn and count the paths that end exactly at amount.
Cost: Exponential: the number of count choices multiplies across denominations, with heavy recomputation of the same (coin, remaining) pairs.
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.