Ways to Make an Amount

You get an array coins of different positive coin values and a non-negative integer amount.

You have an unlimited number of coins of each value. Return the number of different combinations of coins whose values add up to exactly amount.

The order of the coins does not matter. For example, 2 + 3 and 3 + 2 are the same combination and count only once. Two combinations are different only if some coin value is used a different number of times.

If no combination makes the amount, return 0.

Note

If amount is 0, the answer is 1: the empty combination (no coins) makes it.

Hint

Keep an array ways where ways[x] is the number of combinations for amount x, and start with ways[0] = 1. Process the coins one at a time in the outer loop. For each coin c, go through the amounts x from c up to amount and add ways[x - c] to ways[x]. If you put the amounts in the outer loop instead, you count 2 + 3 and 3 + 2 as two different ways.