Coin Change II

Med

#0503Time: O(2^(n + amount)), where `n` is the number of coins. This is a loose upper bound, but the complexity is exponential because many subproblems are recomputed.Space: O(amount). The maximum depth of the recursion stack can be `amount` in the worst case (e.g., using only coins of value 1).1 company

Patterns

Dynamic Programming

Data structures

Array

Companies

Morgan Stanley

Prompt

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

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

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

Approaches

4 approaches with complexity analysis and trade-offs.

This approach attempts to find all possible combinations of coins by using a simple recursive method. It explores every path without storing the results of intermediate calculations. For each coin, it recursively explores two branches: one where the coin is included in the sum (and can be used again), and one where it is skipped, and we move to the next coin. This exhaustive search builds a large recursion tree, leading to exponential complexity.

Algorithm

Define a recursive function countWays(coins, index, amount).
Base Case 1: If amount is 0, it means we have found a valid combination. Return 1.
Base Case 2: If amount becomes negative or if we have considered all coins (index >= coins.length), it's an invalid path. Return 0.
Recursive Step: The total number of ways is the sum of two possibilities:
1. Ways by including the current coin coins[index]: countWays(coins, index, amount - coins[index]). We stay at the same index as we can use the coin multiple times.
2. Ways by excluding the current coin coins[index]: countWays(coins, index + 1, amount). We move to the next coin.
The final result is the sum of these two recursive calls.

Walkthrough

The core idea is to use a helper function, say countWays(coins, index, amount), which calculates the number of ways to make the amount using coins from index onwards.

The recursion unfolds as follows:

Base Cases: The recursion terminates when we either successfully make the amount (amount == 0), in which case we've found one valid combination, or when we reach an invalid state (amount < 0 or no more coins to consider), where we've found zero combinations.
Recursive Logic: For any given state (index, amount), we branch into two decisions:
1. Use the coin coins[index]: We subtract its value from the amount and make a recursive call countWays(coins, index, amount - coins[index]). The index remains the same to allow for multiple uses of the same coin.
2. Skip the coin coins[index]: We move to the next coin by making a recursive call countWays(coins, index + 1, amount). The total number of combinations for the state (index, amount) is the sum of the results from these two branches. While straightforward, this method is highly inefficient because it re-computes solutions for the same (index, amount) states repeatedly.

1class Solution {2    public int change(int amount, int[] coins) {3        return countWays(coins, 0, amount);4    }5 6    private int countWays(int[] coins, int index, int amount) {7        // Base case: If amount is 0, we found one combination.8        if (amount == 0) {9            return 1;10        }11        // Base case: If amount is negative or no more coins, no solution.12        if (amount < 0 || index >= coins.length) {13            return 0;14        }15 16        // Case 1: Include the coin at the current index.17        // We can use the same coin again, so we stay at the same index.18        int waysWithCurrentCoin = countWays(coins, index, amount - coins[index]);19 20        // Case 2: Exclude the coin at the current index.21        // Move to the next coin.22        int waysWithoutCurrentCoin = countWays(coins, index + 1, amount);23 24        return waysWithCurrentCoin + waysWithoutCurrentCoin;25    }26}

Complexity

Time

O(2^(n + amount)), where `n` is the number of coins. This is a loose upper bound, but the complexity is exponential because many subproblems are recomputed.

Space

O(amount). The maximum depth of the recursion stack can be `amount` in the worst case (e.g., using only coins of value 1).

Trade-offs

Pros

Simple to understand and implement.
Directly translates the problem's combinatorial nature into code.

Cons

Extremely inefficient due to exponential time complexity.
Leads to a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial inputs.
Recalculates the same subproblems numerous times.

This approach, also known as Top-Down Dynamic Programming, significantly optimizes the brute-force recursion. It uses a memoization table (typically a 2D array) to store the results of subproblems. When the recursive function is called with a specific set of parameters (e.g., coin index and remaining amount), it first checks if the solution for this subproblem has already been calculated. If it has, it returns the stored value; otherwise, it computes the solution, stores it in the table, and then returns it. This prevents redundant calculations for the same subproblem.

Algorithm

Create a 2D memoization table, memo[n][amount+1], where n is the number of coins. Initialize it with a sentinel value (e.g., null or -1) to indicate uncomputed states.
Use the same recursive structure as the brute-force approach: countWays(coins, index, amount).
Memoization Check: At the beginning of the function, check if memo[index][amount] has already been computed. If so, return the stored value immediately.
Compute and Store: If the state is not memoized, compute the result by making the two recursive calls (include the current coin and exclude it).
Before returning, store the computed result in memo[index][amount] to avoid re-computation in the future.

Walkthrough

We enhance the previous recursive solution by adding a cache, memo, to store the results of countWays(index, amount). The state is defined by the current coin index and the remaining amount.

A 2D array memo[coins.length][amount + 1] is used. memo[i][j] will store the number of ways to make amount j using coins from index i onwards.
Before computing the result for (index, amount), we check memo[index][amount]. If it's not the initial sentinel value, we've solved this subproblem before and can return the stored result.
If the result is not in our memo table, we perform the same recursive calculations as in the brute-force approach.
Crucially, after computing the result, we store it in memo[index][amount] before returning. This ensures that any future call with the same index and amount will be an O(1) lookup.

This technique transforms the exponential complexity of the naive recursion into a polynomial time solution by ensuring each unique subproblem is solved only once.

1class Solution {2    private Integer[][] memo;3 4    public int change(int amount, int[] coins) {5        memo = new Integer[coins.length][amount + 1];6        return countWays(coins, 0, amount);7    }8 9    private int countWays(int[] coins, int index, int amount) {10        if (amount == 0) {11            return 1;12        }13        if (amount < 0 || index >= coins.length) {14            return 0;15        }16        if (memo[index][amount] != null) {17            return memo[index][amount];18        }19 20        // Case 1: Include the coin at the current index.21        int waysWithCurrentCoin = countWays(coins, index, amount - coins[index]);22 23        // Case 2: Exclude the coin at the current index.24        int waysWithoutCurrentCoin = countWays(coins, index + 1, amount);25 26        memo[index][amount] = waysWithCurrentCoin + waysWithoutCurrentCoin;27        return memo[index][amount];28    }29}

Complexity

Time

O(n * amount). The number of states is `n * amount`, and each state is computed once. The computation for each state involves constant time work (addition and recursive calls with memoization checks).

Space

O(n * amount). This is dominated by the size of the memoization table. The recursion stack also contributes up to O(amount) space.

Trade-offs

Pros

Drastically improves performance over brute-force by eliminating redundant computations.
Guaranteed to solve each subproblem only once.
Often more intuitive to write than the bottom-up (tabulation) approach as it follows the logical recursive structure of the problem.

Cons

Requires O(n * amount) space for the memoization table, which can be large.
Still has the overhead associated with recursion, although much less than the brute-force approach.

This approach, also known as Bottom-Up Dynamic Programming or Tabulation, solves the problem iteratively. It builds a 2D table, dp, where dp[i][j] stores the number of ways to make amount j using only the first i coins. The table is filled from smaller subproblems (smaller amounts and fewer coins) to larger ones, ultimately computing the solution for the target amount using all available coins. This avoids recursion and its associated overhead.

Algorithm

Create a 2D DP table dp[n+1][amount+1], where n is the number of coins.
dp[i][j] will represent the number of combinations to make amount j using the first i coins.
Initialization: Set the first column dp[i][0] = 1 for all i from 0 to n. This signifies that there is one way to make an amount of 0 (by choosing no coins).
Iteration: Loop through the coins i from 1 to n and for each coin, loop through the amounts j from 1 to amount.
Transition: For each dp[i][j], the value is calculated as:
- The number of ways without using the i-th coin: dp[i-1][j].
- Plus, if j >= coins[i-1], the number of ways using the i-th coin: dp[i][j - coins[i-1]].
The final answer is the value in dp[n][amount].

Walkthrough

The tabulation method constructs the solution iteratively. We define a 2D array dp[n+1][amount+1].

Meaning: dp[i][j] stores the number of combinations to form amount j using the first i coins (from coins[0] to coins[i-1]).
Initialization: The base case is making an amount of 0. This can always be done in one way (by picking no coins), regardless of how many coins are available. Therefore, dp[i][0] = 1 for all i.
State Transition: We fill the table row by row (for each coin) and column by column (for each amount). For each cell dp[i][j], we consider the i-th coin (coins[i-1]):
1. Don't use the i-th coin: The number of ways is simply the number of ways to make amount j using the first i-1 coins, which is dp[i-1][j].
2. Use the i-th coin: If the coin's value coins[i-1] is not greater than the current amount j, we can use it. The number of ways to do this is equal to the number of ways to form the remaining amount, j - coins[i-1], using the first i coins. This is given by dp[i][j - coins[i-1]]. We use dp[i] (not dp[i-1]) because we can use the i-th coin multiple times.

The final recurrence is dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j - coins[i-1]] : 0). The answer is found at dp[n][amount].

1class Solution {2    public int change(int amount, int[] coins) {3        int n = coins.length;4        int[][] dp = new int[n + 1][amount + 1];5 6        // Base case: 1 way to make amount 07        for (int i = 0; i <= n; i++) {8            dp[i][0] = 1;9        }10 11        for (int i = 1; i <= n; i++) {12            for (int j = 1; j <= amount; j++) {13                // Ways without using coin i is the same as ways using first i-1 coins14                dp[i][j] = dp[i-1][j];15                // If we can use coin i16                if (j >= coins[i-1]) {17                    // Add ways by using coin i18                    dp[i][j] += dp[i][j - coins[i-1]];19                }20            }21        }22 23        return dp[n][amount];24    }25}

Complexity

Time

O(n * amount) due to the two nested loops iterating over the number of coins and the target amount.

Space

O(n * amount) for the 2D DP table.

Trade-offs

Pros

Avoids recursion overhead, which can lead to better performance than memoization in some cases.
The iterative nature can be easier to analyze and debug for some developers.

Cons

Requires O(n * amount) space, which can be prohibitive for very large inputs.

This is the most optimized solution, improving upon the 2D DP approach by reducing its space complexity. By observing the state transition dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]], we can see that to compute the values for the current coin i, we only need the values from the previous coin i-1 and the already computed values for the current coin i at smaller amounts. This dependency allows us to use a single 1D array of size amount + 1, effectively collapsing the 2D table into one row that gets updated for each coin.

Algorithm

Create a 1D DP array dp of size amount + 1 and initialize all elements to 0.
Initialization: Set dp[0] = 1. This is the base case, representing one way to make an amount of 0 (by choosing no coins).
Iteration: Loop through each coin in the coins array (outer loop).
For each coin, iterate from j = coin up to amount (inner loop).
Transition: Update dp[j] by adding the number of ways to make the amount j - coin. The formula is dp[j] = dp[j] + dp[j - coin].
The final answer is the value in dp[amount].

Walkthrough

This approach optimizes the space complexity of the bottom-up DP solution from O(n * amount) to O(amount).

We use a 1D array, dp, of size amount + 1. Here, dp[j] will store the number of combinations to make amount j using the coins considered so far.

Initialization: We start with dp[0] = 1, as there's one way to make an amount of zero. All other dp[j] are implicitly 0.
Iteration: The key is the order of the loops. We must iterate through the coins in the outer loop and the amounts in the inner loop.

1// Outer loop: Iterate through each coin2for (int coin : coins) {3    // Inner loop: Iterate through amounts4    for (int j = coin; j <= amount; j++) {5        // Update dp[j]6        dp[j] += dp[j - coin];7    }8}

Let's analyze the update dp[j] += dp[j - coin]. When we are processing a particular coin, the value dp[j] (before the update) represents the number of ways to make amount j using the previous coins. The value dp[j - coin] represents the total number of ways to make amount j - coin using all coins up to and including the current coin (because the inner loop for j goes from low to high, dp[j - coin] would have been updated in the same pass). By adding dp[j - coin] to dp[j], we are effectively adding the combinations that use the current coin to the combinations that don't.

This loop ordering correctly models the 'unbounded' nature of the problem (using a coin multiple times). The final answer is dp[amount].

1class Solution {2    public int change(int amount, int[] coins) {3        // dp[i] will store the number of combinations to make amount i.4        int[] dp = new int[amount + 1];5        6        // Base case: There is one way to make amount 0 (by choosing no coins).7        dp[0] = 1;8        9        // Iterate through each coin.10        for (int coin : coins) {11            // For each coin, update the dp array for all amounts from the coin's value up to the target amount.12            for (int j = coin; j <= amount; j++) {13                // The number of ways to make amount j is the sum of:14                // 1. Ways to make amount j without using the current coin (value already in dp[j] from previous coins).15                // 2. Ways to make amount (j - coin) and then adding the current coin.16                dp[j] += dp[j - coin];17            }18        }19        20        return dp[amount];21    }22}

Complexity

Time

O(n * amount), where `n` is the number of coins. We have two nested loops.

Space

O(amount) for the 1D DP array.

Trade-offs

Pros

Most efficient solution in terms of space complexity.
Iterative approach avoids recursion overhead.
Excellent time complexity for this class of problem.

Cons

The logic, particularly the significance of the loop order, can be less intuitive to grasp initially compared to the 2D DP approach.

Solutions

Solution

1class Solution : def change ( self , amount : int , coins : List [ int ]) -> int : dp = [ 0 ] * ( amount + 1 ) dp [ 0 ] = 1 for coin in coins : for j in range ( coin , amount + 1 ): dp [ j ] += dp [ j - coin ] return dp [ - 1 ]

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

1class Solution { public: int change ( int amount , vector < int >& coins ) { vector < int > dp ( amount + 1 ); dp [ 0 ] = 1 ; for ( auto coin : coins ) { for ( int j = coin ; j <= amount ; ++ j ) { dp [ j ] += dp [ j - coin ]; } } return dp [ amount ]; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution : def change ( self , amount : int , coins : List [ int ]) -> int : dp = [ 0 ] * ( amount + 1 ) dp [ 0 ] = 1 for coin in coins : for j in range ( coin , amount + 1 ): dp [ j ] += dp [ j - coin ] return dp [ - 1 ]

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

1class Solution { public: int change ( int amount , vector < int >& coins ) { vector < int > dp ( amount + 1 ); dp [ 0 ] = 1 ; for ( auto coin : coins ) { for ( int j = coin ; j <= amount ; ++ j ) { dp [ j ] += dp [ j - coin ]; } } return dp [ amount ]; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.