Fewest coins that cover every amount up to a limit

You are given a list of coin denominations (positive integers) and an integer max_amount. You may take any number of coins of each denomination.

Choose a multiset of coins so that every integer amount from 1 to max_amount can be paid exactly with some subset of the chosen coins. Each chosen coin can be used at most once per amount. Return the minimum number of coins you must choose. If no choice works, return -1.

def min_coins_to_cover(denominations: list[int], max_amount: int) -> int: ...

Constraints

• 0 <= len(denominations) <= 10^5, 1 <= denominations[i] <= 10^18. Duplicates may appear.
• 0 <= max_amount <= 10^18. Return 0 when max_amount is 0.
• Your solution must not take time proportional to max_amount.

Example 1

• Input: denominations = [1, 2, 5], max_amount = 10
• Output: 4
• Explanation: The coins 1, 2, 2, 5 cover every amount from 1 to 10. For example, 4 = 2 + 2, 8 = 1 + 2 + 5 and 9 = 2 + 2 + 5. No set of 3 coins can do it.

Example 2

• Input: denominations = [2, 5], max_amount = 10
• Output: -1
• Explanation: The amount 1 can never be formed.

Reconstructed from the reported question; details may differ from what interviewers ask.