Coin Change 2
HardCoins in the outer loop, or you count orders
Problem
Count the number of ways to make an amount using coins with unlimited supply.
Count combinations by adding each coin type one at a time so orderings aren't double-counted.
The idea
Count combinations by iterating coins on the outside and amounts on the inside, so each coin is considered once per amount. Swapping the loops counts permutations instead, which is a different problem.
The trick
- Coins outer, amount inner — this ordering is the whole subtlety.
- dp[0] = 1: one way to make nothing.
- O(amount × coins).
Step 1 of 8. dp[a] = fewest coins to make amount a. Coins 1, 3, 4. dp[0] = 0, the rest start at ∞. Values: 0, ∞, ∞, ∞, ∞, ∞, ∞.
Unbounded knapsack.
1const dp = Array(amount + 1).fill(Infinity);2dp[0] = 0;3for (let a = 1; a <= amount; a++)4 for (const c of coins)5 if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);6return dp[amount] === Infinity ? -1 : dp[amount];Input
- array
- [0, ∞, ∞, ∞, ∞, ∞, ∞]
Memory
- a
- —
- a−c
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- coins = [1, 2, 5], amount = 5
- Output:
- 4
- Explanation:
- 4 different ways to make 5.
Example 2
- Input:
- coins = [2], amount = 3
- Output:
- 0
- Explanation:
- Odd amount from 2s is impossible → 0.
Example 3
- Input:
- coins = [1], amount = 0
- Output:
- 1
- Explanation:
- One way to make 0 (use nothing).
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.