Coin Change: Number of Ways

With an unlimited number of coins of each value, how many different combinations make exactly amount? Order doesn’t matter: 1 + 2 and 2 + 1 are the same. Amount 0 has one combination (no coins).

Examples

Example 1

Input:  amount = 5, coins = [1, 2, 5]
Output: 4

5 · 2+2+1 · 2+1+1+1 · 1+1+1+1+1.