518. Coin Change II

Practice Coin Change II for free on NudgeCode: Medium, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Given coin values coins (unlimited supply of each) and a total amount, count the different combinations of coins that sum to amount. Order does not matter: 1+2 and 2+1 are the same combination. An amount of 0 has exactly one combination (no coins).

Example

amount = 5, coins = [1,2,5]  ->  4   (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)
amount = 3, coins = [2]      ->  0

Constraints

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