771. Coin Change — Minimum Coins (Recursive)

You are given an array of positive integers coins representing coin denominations, and a non-negative integer amount. Return the FEWEST number of coins that sum to amount. You may use each coin an UNLIMITED number of times. If it is not possible to reach the amount, return -1. By convention, 0 coins are needed for amount = 0. Implement with recursion + memoization.

Input: An integer array coins and a non-negative integer amount, formatted as "[c1,c2,...], amount".

Output: Return an integer — the minimum number of coins, or -1 if unreachable.

Examples

Input: [1,2,5], 11
Output: 3
Explanation: 5 + 5 + 1 = 11.

Input: [2], 3
Output: -1
Explanation: Cannot make 3 with only 2s.

Input: [1], 0
Output: 0
Explanation: Zero coins needed for amount 0.

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 1000
• 0 <= amount <= 1000

Asked by