395. Coin Change II
You are given an integer amount and an array coins of distinct coin denominations. You have an unlimited supply of every denomination.
Return the number of different combinations of coins whose values sum to exactly amount. Two selections count as the same combination when they use the same multiset of coins — order is irrelevant, so 2 + 3 and 3 + 2 are one combination, not two.
If amount is 0, the answer is 1: the empty combination. If no selection reaches amount, return 0. The answer is guaranteed to fit in a signed 32-bit integer.
Example 1:
Input: amount = 6, coins = [1, 2, 5]
Output: 5
Explanation: The five combinations are 5+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, and six 1s.
Example 2:
Input: amount = 7, coins = [4, 6]
Output: 0
Explanation: Every sum built from 4s and 6s is even, so the odd target 7 is unreachable.
Example 3:
Input: amount = 0, coins = [3, 7]
Output: 1
Explanation: Amount 0 is made exactly one way: take no coins at all.
Constraints:
- 1 ≤ coins.length ≤ 300
- 1 ≤ coins[i] ≤ 5000, all values distinct
- 0 ≤ amount ≤ 5000
- The answer fits in a signed 32-bit integer
Hints:
"Combinations, not permutations" is the heart of the problem. If you count by asking "which coin comes first?" you will count 2+3 and 3+2 separately. Instead, decide everything about one denomination before moving to the next.
Keep dp[a] = ways to build amount a using only the denominations processed so far. For each new coin c, run a from c up to amount doing dp[a] += dp[a - c]. Coin-outer / amount-inner counts combinations; the reversed nesting counts ordered sequences instead.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: amount = 6, coins = [1, 2, 5]
Expected output: 5