Return a Minimum-Coin Change Breakdown
Problem statement
Make amount using the fewest coins from the denominations in coins. Every denomination is available in unlimited quantity. Return an integer array with one count per denomination, in the same order as coins.
If several combinations use the minimum number of coins, prefer the one using more coins of the largest denomination; if still tied, compare counts at the next smaller denomination, and continue downwards. Return an empty array if making the amount is impossible. For amount zero, return one zero for each denomination.
The input may use arbitrary positive denominations. Choosing the largest coin first is sufficient for some systems, including [1,5,10,25], but is not a general solution.
Function
minimumCoinBreakdown(coins: int[], amount: int) → int[]Examples
Example 1
coins = [1,5,10,25]amount = 33return = [3,1,0,1]Use one 25, one 5, and three 1 coins. Their value is 25 + 5 + 3 = 33 and their count is 5, which is minimum. Counts follow the input denomination order.
Example 2
coins = [1,3,4]amount = 6return = [0,2,0]Two 3 coins make 6. Taking a 4 first would require two 1 coins and use three coins. Return the two-coin solution.
Example 3
coins = [2,4]amount = 3return = []Every available coin has even value, so no combination can total the odd amount 3. Return an empty array.
Constraints
1 <= coins.length <= 201 <= coins[i] <= 1000- The denominations are strictly increasing.
0 <= amount <= 10000