Refund Chunk Denominations
A UPI payment gateway settles refunds by breaking the amount into configurable chunk sizes (the merchant picks which chunk values its reconciliation supports). To minimise ledger entries, refund a given amount using the fewest chunks possible.
Problem
Given a list of positive chunk denominations and a target amount, return the minimum number of chunks (denominations may be reused any number of times) that sum exactly to amount, or -1 if it cannot be formed.
Input
An array denoms of length m (1 ≤ m ≤ 50) of positive ints, and amount (0 ≤ amount ≤ 10^4).
Output
A single integer — the minimum chunk count, or -1.
Constraints
- 1 ≤ m ≤ 50; denominations are positive
- 0 ≤ amount ≤ 10,000
- Each denomination may be used unlimited times
Examples
Example 1
Input
denoms = [1, 3, 4], amount = 6
Output
2
3 + 3 = 6 uses two chunks; the greedy 4 + 1 + 1 would use three.
Example 2
Input
denoms = [2], amount = 3
Output
-1
Only even totals are reachable with a single denomination of 2.