Minimum Coins for Change

You're at a till handing back change. You have an unlimited stack of each coin in front of you — say 1s, 2s, and 5s — and you owe the customer some amount. You want to hand over the fewest coins that add up exactly to that amount. Implement coinChange(coins, amount): given the available denominations and a target, return the smallest number of coins that sum to amount, or -1 if no combination of those coins can make it.

The catch that makes this more than counting: grabbing the biggest coin that fits, over and over, does not always give the fewest coins. With coins [1, 3, 4] and a target of 6, biggest-first hands back 4 + 1 + 1 (three coins) when 3 + 3 (two coins) is better. You need to consider every denomination at every step, not just the largest.

Signature

// coins:  number[] — available denominations, each a positive integer.
//                    You have an UNLIMITED supply of each.
// amount: number   — the target total to make (a non-negative integer).
// returns: number  — the FEWEST coins that sum to `amount`,
//                    or -1 if no combination can make it.
function coinChange(coins, amount): number;

Examples

// 5 + 5 + 1 = 11 uses three coins; nothing does it in two.
coinChange([1, 2, 5], 11); // → 3

// 3 + 3 = 6 in two coins. Biggest-first (4 + 1 + 1) would say three — wrong.
coinChange([1, 3, 4], 6); // → 2

// Every total made from 2s is even, so 3 is unreachable.
coinChange([2], 3); // → -1

// Making zero needs zero coins, regardless of the denominations.
coinChange([1, 2, 5], 0); // → 0

Notes

• Unlimited supply. Each denomination can be used any number of times (including zero).
• amount of 0 returns 0. The empty selection sums to zero, so no coins are needed.
• Impossible totals return -1. If no combination sums exactly to amount (e.g. only [2] to make 3), return -1 — not 0, not Infinity.
• Coins are positive integers. No zero coins, no negatives, no fractions. The amount is a non-negative integer too.
• Denominations may arrive unsorted and may repeat. Don't assume coins is sorted or deduplicated; your answer must not depend on either.
• Don't worry about which specific coins were used — only the count matters. Returning the actual coins is covered in Going further.