Coin Change II
Medium · 2-D Dynamic Programming
You are given a target amount of money and a list of distinct coin denominations, each available in unlimited quantity. Count how many different combinations of coins add up exactly to the target amount, where combinations are considered the same regardless of the order coins are picked in. Return that count.
Examples
Input: amount = 5, coins = [1,2,5]
Output: 4
Why: The valid combinations are 5; 2+2+1; 2+1+1+1; 1+1+1+1+1, giving a count of 4.Input: amount = 3, coins = [2]
Output: 0
Why: No combination of 2's can ever total 3, so there are zero ways.Input: amount = 0, coins = [7,3]
Output: 1
Why: There is exactly one way to make 0: use no coins at all.Constraints
0 <= amount <= 5000, 1 <= coins.length <= 300, 1 <= coins[i] <= 5000, all coins values are distinct
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Coin Change II. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.