Skip to content
Onsite
24 / 48

Coin Change II

MediumP2Coding

Given an amount and a list of distinct coin values coins (each coin may be used any number of times), return the number of different combinations of coins that make exactly amount. Combinations that differ only in order count once (1 + 2 and 2 + 1 are the same). An amount of 0 has one combination, the empty one.

Example 1

Input
amount = 5, coins = [1,2,5]
Output
4
Why
Four combinations: 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

Example 2

Input
amount = 3, coins = [2]
Output
0
Why
Odd amounts cannot be made from 2s.

Example 3

Input
amount = 10, coins = [10]
Output
1

Constraints

  • 0 <= amount <= 5000
  • 0 <= coins.length <= 20
  • 1 <= coins[i] <= 5000, all distinct
  • The answer fits in a 53-bit integer.

Hints

Run checks the 3 visible tests, Submit all 12.