Coin Change

Problem

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.

Return the fewest number of coins that you need to make up the exact target amount. If it is impossible to make up the amount, return -1.

You may assume that you have an unlimited number of each coin.

Examples

Example 1:

Input: coins = [1,5,10], amount = 12

Output: 3

Explanation: 12 = 10 + 1 + 1. Note that we do not have to use every kind coin available.

Example 2:

Input: coins = [2], amount = 3

Output: -1

Explanation: The amount of 3 cannot be made up with coins of 2.

Example 3:

Input: coins = [1], amount = 0

Output: 0

Explanation: Choosing 0 coins is a valid way to make up 0.

Constraints

• 1 <= coins.length <= 10
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10000

You should aim for a solution with O(n * t) time and O(t) space, where n is the number of coins and t is the given amount.

Solution

Each coin we can use is a branch in a tree. DFS can explore all branches, but there is a lot of duplicate work, so we use memoization.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) { return 0; }
        constexpr auto INF = std::numeric_limits<int>::max();
        std::unordered_map<int, int> memory;
 
        std::function<int(int)> dfs;
        dfs = [&](int amount) -> int {
            // Base case
            if (amount == 0) { return 0; }
            // Previously seen result
            if (memory.contains(amount)) { return memory[amount]; }
 
            int result = INF;
            for (const auto &coin : coins) {
                if (amount - coin >= 0) {
                    auto res = dfs(amount - coin);
                    if (res < INF) {
                        result = std::min(result, res + 1);
                    }
                }
            }
            memory[amount] = result;
            return result;
        };
        auto result = dfs(amount);
        return result == INF ? -1 : result;
    }
};