Coin Change II
Part of Practice: Grids & Two Strings
You are given an integer amount and an array coins of distinct coin denominations. You have unlimited copies of every coin. Count how many different combinations of coins add up exactly to amount — two selections count as the same combination if they use the same coins in the same quantities, regardless of order. If the amount cannot be made, return 0. An amount of 0 has exactly one combination: use no coins.
Constraints: 1 <= coins.length <= 300, 1 <= coins[i] <= 5000 (all distinct), 0 <= amount <= 5000. The answer fits in a signed 32-bit integer.
Examples
- Input:
- amount = 5, coins = [1, 2, 5]
- Output:
- 4
The combinations are 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1.
- Input:
- amount = 3, coins = [2]
- Output:
- 0
Only even amounts can be formed with a 2-coin.
- Input:
- amount = 10, coins = [10]
- Output:
- 1
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.