Fewest Coins for an Amount with Unlimited or Single-Use Coins

You are given coin values coins and a target amount. Return the fewest coins whose values add up to exactly amount, or -1 if no selection of coins does. The interview asked this in two forms, and unlimited selects between them:

• unlimited = True: every value in coins is a denomination with an unlimited supply, so a value can be used any number of times.
• unlimited = False: every element of coins is one physical coin that can be used at most once; equal values in the list are separate coins.

The report describes the round only as the classic coin-change problem followed by the variant in which each coin can be used at most once; this version asks for the fewest coins in both forms.

Function Signature

def fewest_coins(coins: list[int], amount: int, unlimited: bool) -> int:

Rules

• amount = 0 needs no coins, so the answer is 0 in both forms.
• The answer counts coins, not distinct values: using the value 3 twice counts as two coins.
• Return -1 when amount cannot be formed exactly.

Constraints

• 1 <= len(coins) <= 100
• 1 <= coins[i] <= 10^4
• 0 <= amount <= 10^4

Examples

Example 1

Input: coins = [1, 3, 4], amount = 6, unlimited = True
Output: 2

3 + 3 uses two coins. Taking the largest coin first gives 4 + 1 + 1, which uses three.

Example 2

Input: coins = [1, 3, 4], amount = 6, unlimited = False
Output: -1

With each coin usable once, the reachable totals are 1, 3, 4, 5, 7 and 8, so 6 cannot be formed.

Example 3

Input: coins = [2, 5, 2, 2], amount = 6, unlimited = False
Output: 3

The three separate 2-coins make 6; the 5-coin is not part of any selection that sums to 6.