Coin Change

mediumDynamic Programming+20 XPTime limit 2s

You have coins of n denominations (unlimited supply of each). Find the fewest coins that add up to amount, or -1 if it is impossible.

Input:

line 1: n amount
line 2: the n coin values

Output: the minimum number of coins, or -1.

Constraints: 1 ≤ n ≤ 12, 1 ≤ coin ≤ 10⁴, 0 ≤ amount ≤ 10⁴. Greedy (biggest coin first) is wrong — try coins 1 3 4 with amount 6.

Sample input 1

3 11
1 2 5

Sample output 1

Sample input 2

1 3
2

Sample output 2

-1

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…