# Coin Change II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/coin-change-ii)
Canonical: https://scaleengineer.com/dsa/problems/coin-change-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
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
## Brute-Force Recursion
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.
**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).
**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.
### Explanation
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.

```java
class Solution {
    public int change(int amount, int[] coins) {
        return countWays(coins, 0, amount);
    }

    private int countWays(int[] coins, int index, int amount) {
        // Base case: If amount is 0, we found one combination.
        if (amount == 0) {
            return 1;
        }
        // Base case: If amount is negative or no more coins, no solution.
        if (amount < 0 || index >= coins.length) {
            return 0;
        }

        // Case 1: Include the coin at the current index.
        // We can use the same coin again, so we stay at the same index.
        int waysWithCurrentCoin = countWays(coins, index, amount - coins[index]);

        // Case 2: Exclude the coin at the current index.
        // Move to the next coin.
        int waysWithoutCurrentCoin = countWays(coins, index + 1, amount);

        return waysWithCurrentCoin + waysWithoutCurrentCoin;
    }
}
```
### 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.

## Top-Down Dynamic Programming with Memoization
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    private Integer[][] memo;

    public int change(int amount, int[] coins) {
        memo = new Integer[coins.length][amount + 1];
        return countWays(coins, 0, amount);
    }

    private int countWays(int[] coins, int index, int amount) {
        if (amount == 0) {
            return 1;
        }
        if (amount < 0 || index >= coins.length) {
            return 0;
        }
        if (memo[index][amount] != null) {
            return memo[index][amount];
        }

        // Case 1: Include the coin at the current index.
        int waysWithCurrentCoin = countWays(coins, index, amount - coins[index]);

        // Case 2: Exclude the coin at the current index.
        int waysWithoutCurrentCoin = countWays(coins, index + 1, amount);

        memo[index][amount] = waysWithCurrentCoin + waysWithoutCurrentCoin;
        return memo[index][amount];
    }
}
```
### 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.

## Bottom-Up Dynamic Programming (2D DP)
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.
**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.
**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.
### Explanation
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]`.

```java
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

        // Base case: 1 way to make amount 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                // Ways without using coin i is the same as ways using first i-1 coins
                dp[i][j] = dp[i-1][j];
                // If we can use coin i
                if (j >= coins[i-1]) {
                    // Add ways by using coin i
                    dp[i][j] += dp[i][j - coins[i-1]];
                }
            }
        }

        return dp[n][amount];
    }
}
```
### 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]`.

## Space-Optimized Bottom-Up DP (1D DP)
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.
**Time:** O(n * amount), where `n` is the number of coins. We have two nested loops. · **Space:** O(amount) for the 1D DP array.
**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.
### Explanation
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.

```java
// Outer loop: Iterate through each coin
for (int coin : coins) {
    // Inner loop: Iterate through amounts
    for (int j = coin; j <= amount; j++) {
        // Update dp[j]
        dp[j] += dp[j - coin];
    }
}
```

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]`.

```java
class Solution {
    public int change(int amount, int[] coins) {
        // dp[i] will store the number of combinations to make amount i.
        int[] dp = new int[amount + 1];
        
        // Base case: There is one way to make amount 0 (by choosing no coins).
        dp[0] = 1;
        
        // Iterate through each coin.
        for (int coin : coins) {
            // For each coin, update the dp array for all amounts from the coin's value up to the target amount.
            for (int j = coin; j <= amount; j++) {
                // The number of ways to make amount j is the sum of:
                // 1. Ways to make amount j without using the current coin (value already in dp[j] from previous coins).
                // 2. Ways to make amount (j - coin) and then adding the current coin.
                dp[j] += dp[j - coin];
            }
        }
        
        return dp[amount];
    }
}
```
### 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]`.

# Solutions
### Python

```python
class 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 ]
```

### Java

```java
class 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 ]; } }
```

### CPP

```cpp
class 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 ]; } };
```