All problems

Coin Change II

Medium · dynamic programming

You have coins of several denominations in coins, and as many copies of each denomination as you want. Given a target amount of money, return the number of different combinations of coins that add up to exactly amount.

Two combinations are the same if they use the same number of each denomination, whatever order the coins are picked in. So 2 + 1 and 1 + 2 count once.

An amount of 0 has exactly one combination, the empty one, so return 1. If no combination works, return 0.

Examples

Example 1

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

Output: 4

5, 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1.

Example 2

Input: coins = [3], amount = 2

Output: 0

A 3 is already too big, so 2 cannot be made.

Example 3

Input: coins = [4, 7], amount = 0

Output: 1

Using no coins at all is the single combination.

Constraints

• 1 <= len(coins) <= 100
• 1 <= coins[i] <= 500, and all coins are distinct.
• 0 <= amount <= 500
• The answer, and the number of combinations for every smaller amount, fit in a 32-bit signed integer.