Coin Change II

Problem

You are given a list of distinct coin denominations coins and a target amount. Each denomination may be used any number of times. Count how many different combinations of coins sum exactly to amount. Two combinations are the same if they use the same number of each denomination; order does not matter, so 2 + 3 and 3 + 2 are one combination. Return 0 if the amount cannot be formed.

• coins holds up to a few hundred distinct denominations.
• Each denomination and amount fit comfortably in a 32-bit range, and so does the answer.

Examples

• coins = [1, 3, 4], amount = 7 → 5: 4+3, 4+1+1+1, 3+3+1, 3+1+1+1+1, 1+1+1+1+1+1+1.
• coins = [2], amount = 3 → 0. Odd amounts are unreachable with only 2s.
• coins = [9], amount = 9 → 1. One coin, one way.

Hints

1. Write a recursive function that counts ways. If it treats 2+3 and 3+2 as different, what extra decision could you fix to avoid that?
2. Process denominations one at a time. For each coin, decide how the number of ways to reach every amount changes once that coin becomes available.
3. Unbounded knapsack with the coin loop on the outside: ways[a] += ways[a - c] for each coin c, for a from c up to amount.