Coin Change Problem

Problem Given an array of coin denominations and a target amount, find the fewest coins that sum exactly to the amount, or report that the amount cannot be formed.

Input / Output

• Input: coins — an array of distinct positive denominations — and an integer amount.
• Output: the minimum number of coins summing to amount; -1 if no combination reaches it.

Constraints

• Unlimited supply of each denomination.
• 1 <= coins.length <= 12, 0 <= amount <= 10^4 typically.
• amount = 0 → 0, taking no coins.
• Greedy (take the largest coin that fits, repeat) is wrong for arbitrary denominations — it only works for canonical systems like [1,5,10,25].

Example

• coins = [1,2,5], amount = 11 → 3 (5+5+1).
• coins = [2], amount = 3 → -1; parity makes it unreachable.
• coins = [1,3,4], amount = 6 → 2 (3+3), whereas greedy takes 4+1+1 = 3 coins — the case that disproves the greedy answer.