Fewest Coins for the Fare
The bus fare is fare cents and the driver only takes exact change. Your pocket holds an unlimited number of coins of each value in coins. Return the smallest number of coins whose values add up to exactly fare. If no combination of the coins can make the fare, return -1. A fare of 0 needs no coins, so return 0 in that case.
Example 1
coins [1,5,12]
fare 15
returns 3
Three 5s make 15; starting with the 12 would need 12 + 1 + 1 + 1, which is four coins.
Example 2
coins [4,6]
fare 7
returns -1
Every total made from 4s and 6s is even, so 7 is impossible.
Constraints
1 <= len(coins) <= 6, the values are distinct1 <= coins[i] <= 1000 <= fare <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.