Fewest coins to make the amount

Medium

2000 ms limit256 MB memoryDynamic programming Greedy

Stuck?

Show a hint

Work out the best for every amount from 0 upward. For each amount, try every coin as the last one used and take the smallest result.

The ideas behind this problem

Dynamic programming without the mystique Greedy: when the obvious move is the right one

Next in this lesson

Can it be split into two equal halves

Given coin values you have an unlimited supply of, return the fewest coins that add to exactly amount. Return -1 if it cannot be done.

Worked example#

Coins [1, 2, 5], amount 11.

Build up every amount from 0, and for each one try every coin as the last coin used:

amount	best	the last coin that gave it
0	0	nothing needed
1	1	a 1 onto amount 0
2	1	a 2 onto amount 0
3	2	a 1 onto amount 2
4	2	a 2 onto amount 2
5	1	a 5 onto amount 0
6	2	a 1 onto amount 5
...
11	3	a 1 onto amount 10, which was two 5s

Three coins: 5 + 5 + 1.

Why not just take the largest coin each time#

That is the greedy instinct, and with everyday coins it works. It is not correct in general.

Take coins [1, 3, 4] and amount 6. Greedy takes 4, then needs 1 + 1: three coins. The answer is two: 3 + 3.

Taking the 4 looked best and closed off the better route. Because one choice changes what is left, every amount has to be worked out rather than guessed, which is exactly the dynamic programming case.

The shape of the solution#

For each amount from 1 upward, and each coin no larger than it:

best[amount] = min(best[amount], best[amount - coin] + 1)

Start best[0] = 0 and everything else at "impossible". If best[amount] is still impossible at the end, no combination works.

Use a sentinel you cannot reach by accident. amount + 1 works, because no answer can need more coins than the amount itself. Using a maximum integer instead overflows the moment you add 1 to it, which is a favourite bug here.

The cost#

Time O(amount x number of coins). Memory O(amount).

Constraints#

1 <= number of coins <= 12
1 <= coin value <= 1000000
0 <= amount <= 10000

Input

coins is a count then that many integers. Then amount is one integer.

Output

The fewest coins, or -1 if the amount cannot be made.

Examples

Input

3
1 2 5
11

Output

5 + 5 + 1.

Input

3
1 3 4
6

Output

3 + 3. Taking the largest coin first would need three.

Input

1
2
3

Output

-1

Only even amounts can be made from 2s.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.