Coin Change

Medium

dynamic-programmingbfsarray

Given coin denominations coins (unlimited supply) and an amount, return the fewest coins needed to make the amount exactly, or -1 if impossible.

Input

Line 1: space-separated coin values
Line 2: integer amount

Output: the fewest coins, or -1.

Example 1

Input:

1 2 5
11

Output:

5 + 5 + 1.

Example 2

Input:

2
3

Output:

-1

Example 3

Input:

1
0

Output:

Constraints

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 2^31 − 1
0 ≤ amount ≤ 10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Coin Change

Medium

dynamic-programmingbfsarray

Given coin denominations coins (unlimited supply) and an amount, return the fewest coins needed to make the amount exactly, or -1 if impossible.

Input

Line 1: space-separated coin values
Line 2: integer amount

Output: the fewest coins, or -1.

Example 1

Input:

1 2 5
11

Output:

5 + 5 + 1.

Example 2

Input:

2
3

Output:

-1

Example 3

Input:

1
0

Output:

Constraints

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 2^31 − 1
0 ≤ amount ≤ 10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.