Coin Change 2
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
You are given a target amount and an array coins of distinct denominations, with an unlimited supply of each.
Return how many different combinations of coins add up exactly to amount. Combinations are unordered: the same multiset of coins in a different order counts once. If no combination works, return 0.
The answer fits in a signed 32-bit integer.
Examples
Input: amount = 6, coins = [1,2,4] Output: 6
Six combinations: 1·6, 2 + 1·4, 2 + 2 + 1 + 1, 2 + 2 + 2, 4 + 1 + 1 and 4 + 2.
Input: amount = 7, coins = [4] Output: 0
Multiples of 4 never equal 7.
Input: amount = 0, coins = [3] Output: 1
Taking no coins is the one way to make 0.
Constraints
- 1 <= len(coins) <= 300
- 1 <= coins[i] <= 5000
- All values in coins are distinct.
- 0 <= amount <= 5000
Approaches
- Baseline: table, try every count of each coin — time O(n · amount²) in the worst case, space O(n · amount)
Follow-up
Swap the two loops (amount outside, coins inside) and the same recurrence counts ordered sequences instead, so 1 + 2 and 2 + 1 become two ways. Which question does each loop order answer, and why?
Related problems
Start free on Cariara · Coding problems · System design studio
