Coin Change II

NeetCode: Coin Change II · LeetCode: 518. Coin Change II · Difficulty: Medium

Given coin denominations coins (an int[], unlimited supply of each) and an amount, return the number of combinations that make up that amount. Two combinations are the same if they use the same coins in different orders. If no combination works, return 0.

Example

Text

Input:  amount = 5, coins = [1, 2, 5]    Output: 4   (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)
Input:  amount = 3, coins = [2]          Output: 0
Input:  amount = 0, coins = [7]          Output: 1   (use no coins)

Brute force: use or skip each coin type

To count combinations rather than orderings, decide coin types in a fixed order. At coin type i with remaining left to make, either use one more coin of type i (and stay on i, since it can be reused) or move on to type i + 1 for good. Reaching remaining == 0 counts one combination; running out of coin types with something left counts none. The number of branches is exponential and many (i, remaining) pairs repeat.

Java

class Solution {
    private long count(int[] coins, int i, int remaining) {
        if (remaining == 0) {
            return 1;
        }
        if (i == coins.length) {
            return 0;
        }
        long skip = count(coins, i + 1, remaining);
        long take = coins[i] <= remaining ? count(coins, i, remaining - coins[i]) : 0;
        return skip + take;
    }

    public int change(int amount, int[] coins) {
        return (int) count(coins, 0, amount);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[] {1, 2, 5}));
        System.out.println(sol.change(3, new int[] {2}));
        System.out.println(sol.change(0, new int[] {7}));
    }
}

Output

4
0
1

Time: exponential (roughly O(2^(amount + k)) for k coin types in the worst case). Space: O(amount + k).

Better: 2D table (coin types by amount)

dp[i][a] is the number of ways to make a using only the first i coin types. Either you never use coin i - 1 (dp[i-1][a]) or you use it at least once (dp[i][a - coin], staying in the same row because a coin can be reused). Column 0 is 1 everywhere: the empty combination.

Java

class Solution {
    public int change(int amount, int[] coins) {
        int k = coins.length;
        long[][] dp = new long[k + 1][amount + 1];
        for (long[] row : dp) {
            row[0] = 1;
        }
        for (int i = 1; i <= k; i++) {
            int coin = coins[i - 1];
            for (int a = 1; a <= amount; a++) {
                dp[i][a] = dp[i - 1][a];
                if (coin <= a) {
                    dp[i][a] += dp[i][a - coin];
                }
            }
        }
        return (int) dp[k][amount];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[] {1, 2, 5}));
        System.out.println(sol.change(3, new int[] {2}));
        System.out.println(sol.change(0, new int[] {7}));
    }
}

Output

4
0
1

Time: O(k · amount). Space: O(k · amount).

Optimal: 1D table

Each row only reads itself and the row above, so one array is enough: dp[a] holds "ways using the coin types processed so far", and adding a coin is dp[a] += dp[a - coin], iterating amounts upward so that a coin can be reused. The loop order matters: coins in the outer loop, amounts in the inner loop. Swapping them would count 1+2 and 2+1 as different, which answers a different problem (permutations).

Java

class Solution {
    public int change(int amount, int[] coins) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            if (coin == 0) {
                continue; // a zero-valued coin would allow infinitely many combinations
            }
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
        }
        return (int) dp[amount];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[] {1, 2, 5}));
        System.out.println(sol.change(3, new int[] {2}));
        System.out.println(sol.change(0, new int[] {7}));
    }
}

Output

4
0
1

Time: O(k · amount). Space: O(amount).

The problem returns an int, so the final answer is assumed to fit. The tables use long so that intermediate counts cannot wrap silently, and the result is cast back to int at the end.