Leetcode 518. Coin Change II

Hadjshell1/16/26About 2 min

Intuition

This is an unbounded knapsack problem, meaning there is no upper limit on how many copies of each item (coin) can be used. In general, knapsack-type problems are well suited for dynamic programming. If you are not familiar with DP, you may want to take a look at my website, where I provide a detailed explanation of the core ideas.

Approach

In this solution, I use recursive dynamic programming, also known as top-down DP with memoization.

First, let’s define the DP state: memo[amount][i] represents the number of combinations that can sum up to amount using coins from coins[i...] (i.e., from index i to the end of the array).

You might wonder why we need a 2-dimensional DP here. Why not simply define memo[amount], which stores the number of combinations that make up amount? The answer is NO, because this would lead to duplicate combinations. For example, assume coins = [1, 2], amount = 3, and the state transition equation of this 1-dimentional DP would be for coin in coins: dp[amount] += dp[amount - coin]. we would count both [1, 2] and [2, 1] as different solutions, even though they represent the same combination.

To avoid this issue, we adopt an idea similar to Q78. Subsets. For each coin, we decide whether to use it or skip it. If we use a coin, we are allowed to use it again (since the knapsack is unbounded). If we skip it, we move on to the next coin. Crucially, we never go back to previous coins, which prevents duplicate permutations. Hence, the state transition equation is:

If coins[i] > amount, we cannot use this coin:: dp[amount][i] = dp[amount][i + 1];
If coins[i] <= amount, we can choose to use this coin or skip it and look into next left coins: dp[amount][i] = dp[amount - coins[i]][i] + dp[amount][i + 1].

The base case is

amount == 0 means we have found a valid combination, so return dp[0][i] = 1;
amount != 0 && i == coins.length means we have no coins left to use but still have remaining amount, so return dp[amount][coins.length] = 0.

Complexity

Time complexity:
$O(mn)$ : m*n states, each state $O(1)$
Space complexity:
$O(mn)$ : memo array: $O(mn)$ , m*n stacks, each stack $O(1)$

Code

class Solution {
    public int change(int amount, int[] coins) {
        Integer[][] memo = new Integer[amount + 1][coins.length + 1];

        return dp(amount, coins, 0, memo);
    }

    private int dp(int amount, int[] coins, int i, Integer[][] memo) {
        if (amount == 0)
            return 1;

        if (i == coins.length)
            return 0;

        if (memo[amount][i] != null)
            return memo[amount][i];

        int combination = 0;
        if (amount >= coins[i])     combination = dp(amount - coins[i], coins, i, memo) + dp(amount, coins, i + 1, memo);
        else                        combination = dp(amount, coins, i + 1, memo);
        memo[amount][i] = combination;

        return memo[amount][i];
    }
}

If you want to learn more...

We can write our code in bottom-up flavour. And the DP table can be compressed into 1 dimension. The space complexity can be optimised to $O(m)$ . I'll leave this to you to figure out.

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i-coin];
        }
    }
    return dp[amount];
}