Solution: Coin Change

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #322 (Medium): Coin Change

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

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

---

Examples:

Example 1:
Input:	coins = [1,2,5], amount = 11
Output:	3
Explanation:	11 = 5 + 5 + 1

Example 2:
Input:	coins = [2], amount = 3
Output:	-1

Example 3:
Input:	coins = [1], amount = 0
Output:	0

Example 4:
Input:	coins = [1], amount = 1
Output:	1

Example 5:
Input:	coins = [1], amount = 2
Output:	2

---

Constraints:

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

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The naive approach here would be to attempt every permutation of coins (C) to see which ones can reach the target amount (A), but that will easily achieve TLE.

When thinking about how to shorten this, we might realize that in general, using as many larger coins as possible will likely help us get a better answer. Naturally, that means we should start by sorting C.

The next logical idea would be a dynamic programming (DP) solution, where we can keep track of the most ideal results at every step towards the eventual solution. And while there are some good DP solutions for this problem, they're not, however, the best solution.

The best solution here is actually a depth-first search (DFS) solution with recursion, without the need for a DP data structure.

So as we realized earlier, the general strategy here is to use as many of the largest coin available to fill the amount remaining (amt). That rule, unfortunately, does not work every time, however.

Consider the situation in which C = [5,4,1] and A = 8. The basic strategy would lead to coins of [5,1,1,1] to reach 8, but those four coins are definitely not as good as the two coins [4,4].

So we have to modify our rule, and the logical move is to start with our earlier strategy, and just work backwards until we find a good fit. We can take the largest coin, fill up to amt with as many as we can, then fire off the recursive function (rc) onto the next largest coin to repeat the process. When it's done with that recursion, we remove one of the largest coins and fire off the recursion again.

The remaining work is just trimming off as much waste as possible with good conditionals. Obviously, if we go past our target amount, we should stop. And on any given recursion, once we've performed the initial fill the potential results will only get larger as we backtrack, so if the initial fill already produces a result larger than our current best ans, we should close down the entire recursion branch.

---

Implementation:

Both the Java and C++ functions should technically have the ceil() method applied to n, just like Javascript and Python do, but they actually run faster with the inherent flooring of being stored in an int, rather that running them through the extra process.

Java and C++ also had their helper functions extracted out of the main function and thus have an extra argument passed in. In both cases, the ans variable has been hoisted to give it scope for the helper function.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var coinChange = function(C, A) {
    C = Uint32Array.from(C).sort()
    let ans = Infinity
    const rc = (amt, num, cix) => {
        if (!amt) ans = Math.min(num, ans)
        else if (amt > 0 && ~cix) {
            let n = Math.ceil(amt / C[cix])
            if (n + num >= ans) return
            while (~n) rc(amt - n * C[cix], num + n--, cix - 1)
        }
    }
    rc(A, 0, C.length-1)
    return ans < Infinity ? ans : -1
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def coinChange(self, C: List[int], A: int) -> int:
        C.sort()
        ans = 10001
        def rc(amt, num, cix):
            nonlocal ans
            if amt == 0:
                if num < ans: ans = num
            elif amt > 0 and ~cix:
                n = ceil(amt / C[cix])
                if num + n >= ans: return
                for i in range(n, -1, -1):
                    rc(amt - i * C[cix], num + i, cix - 1)
        rc(A, 0, len(C)-1)
        return ans if ans < 10001 else -1

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    int ans = 10001;
    public int coinChange(int[] C, int A) {
        Arrays.sort(C);
        rc(A, 0, C.length-1, C);
        return ans < 10001 ? ans : -1;
    }
    void rc(int amt, int num, int cix, int[] C) {
        if (amt == 0) ans = Math.min(num, ans);
        else if (amt > 0 && cix >= 0) {
            int n = amt / C[cix];
            if (n + num >= ans) return;
            while (n >= 0) rc(amt - n * C[cix], num + n--, cix - 1, C);
        }
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    int ans = 10001;
public:
    int coinChange(vector<int>& C, int A) {
        sort(C.begin(), C.end());
        rc(A, 0, C.size()-1, C);
        return ans < 10001 ? ans : -1;
    }
    void rc(int amt, int num, int cix, vector<int>& C) {
        if (!amt) ans = min(num, ans);
        else if (amt > 0 && ~cix) {
            int n = amt / C[cix];
            if (n + num >= ans) return;
            while (~n) rc(amt - n * C[cix], num + n--, cix - 1, C);
        }
    }
};