Coin Change 2

Coin Change 2 looks like simple counting. But it hides a sharp trap. Count combinations, not arrangements. The interviewer watches how you avoid counting 1 + 2 and 2 + 1 as two different answers. Get the loop order right and you pass.

🎯 The Problem

You get a list of coin values and a target amount. Count how many different ways you can make the amount.

The rules:

• Each coin can be used as many times as you want.
• Order does not matter. So 1 + 2 and 2 + 1 count as the same way.
• Return the count of distinct ways.
• A coin that repeats freely makes this an unbounded knapsack, which means each item can be picked any number of times.

For coins [1, 2, 5] and amount 5, the ways are 5, then 2 + 2 + 1, then 2 + 1 + 1 + 1, then 1 + 1 + 1 + 1 + 1. That makes 4.

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

Explanation: 5 = 5
             5 = 2 + 2 + 1
             5 = 2 + 1 + 1 + 1
             5 = 1 + 1 + 1 + 1 + 1

Here is the problem. We count groups of coins that add up to the amount, treating reorders as the same group.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: at each coin, choose to use it or skip it, and add up the ways.

The idea:

• Track the current coin index and the amount still left.
• Use the coin, which keeps you on the same coin since it can repeat.
• Or skip the coin and move to the next one.

How it works:

• If the amount left reaches zero, that is one full way, so return one.
• If you run out of coins or the amount goes negative, return zero.
• Add the ways from the use choice and the skip choice.

Why it is weak:

• The same coin index and remaining amount get re-solved on many paths.
• The branching grows exponentially.
• Far too slow once the amount is large.

Here is the plain recursion code:

def change(amount, coins):
    def dfs(index, remaining):
        if remaining == 0:
            return 1
        if index == len(coins) or remaining < 0:
            return 0
        take = dfs(index, remaining - coins[index])
        skip = dfs(index + 1, remaining)
        return take + skip

    return dfs(0, amount)

🧠 Approach 2: Memoization (Better)

The idea in one line: cache the answer for each coin index and amount so you solve it once.

The idea:

• The ways for “coin index i with amount a left” never change.
• So store that pair the first time you compute it.

How it works:

• Keep a 2D table keyed by the coin index and the remaining amount.
• The first time you solve a pair, save it.
• Next time the pair appears, read the saved value.

Why it is fast:

• Each pair is solved only once.
• The time drops to O(coins times amount).

Here is the memoized recursion:

from functools import lru_cache


def change(amount, coins):
    @lru_cache(None)
    def dfs(index, remaining):
        if remaining == 0:
            return 1
        if index == len(coins) or remaining < 0:
            return 0
        return dfs(index, remaining - coins[index]) + dfs(index + 1, remaining)

    return dfs(0, amount)

📊 Approach 3: 2D Tabulation (Better)

The idea in one line: build a grid bottom up where each cell counts the ways using the first few coins.

The idea:

• Make a table dp where dp[i][a] is the ways to make amount a using only the first i coins.
• The first column, amount zero, is always one, since picking nothing makes zero.

How it works:

• Ways to make a with the first i coins is the ways without the current coin, the cell above.
• Plus the ways that use the current coin at least once, which is dp[i][a - coin].
• Tabulation fills the grid in order so each cell already has the two cells it needs.

Why it is fine:

• Each cell is filled once.
• The time is O(coins times amount), same as memoization, with no recursion.

Here is the 2D grid filling for coins [1, 2, 5] and amount 5. Each row adds one more coin into the mix.

⚡ Approach 4: Space-Optimized One Row (Best)

The idea in one line: keep one rolling array and loop coins on the outside, amounts low to high.

The idea:

• Each new row of the grid reads only the row above and the current row.
• So you can keep just one row and update it in place.

How it works:

• The outer loop goes over coins.
• The inner loop goes over amounts from the coin value up to the target.
• Add dp[a - coin] into dp[a].

Why the loop order matters:

• Coins on the outside counts combinations, not arrangements.
• It forces every way to use coins in a fixed coin order.
• So 1 + 2 and 2 + 1 collapse into one.

Why it is best:

• One array of size amount plus one is enough.
• Memory drops from O(coins times amount) to O(amount), and it stays just as fast.

Steps to Solve

1. Make an array dp of length amount plus one, filled with zeros. Set dp[0] to 1, since there is one way to make zero.
2. Loop over each coin on the outside. This order is what counts combinations, not arrangements.
3. For each coin, loop the amount from the coin value up to the target.
4. Add dp[a - coin] into dp[a]. This brings in every way that uses the current coin.
5. After all coins, dp[amount] holds the total number of ways.

#include <stdio.h>

int change(int amount, int coins[], int n) {
    int dp[5001] = {0};
    dp[0] = 1;                         // one way to make 0

    for (int i = 0; i < n; i++) {      // coins on the outside
        for (int a = coins[i]; a <= amount; a++) {  // low to high
            dp[a] += dp[a - coins[i]];
        }
    }
    return dp[amount];
}

int main(void) {
    int coins[] = {1, 2, 5};
    int amount = 5;
    printf("%d\n", change(amount, coins, 3));
    return 0;
}

4

#include <iostream>
#include <vector>
using namespace std;

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;                         // one way to make 0

    for (int coin : coins) {           // coins on the outside
        for (int a = coin; a <= amount; a++) {  // low to high
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << change(amount, coins) << endl;
    return 0;
}

4

public class CoinChange2 {
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;                         // one way to make 0

        for (int coin : coins) {           // coins on the outside
            for (int a = coin; a <= amount; a++) {  // low to high
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = { 1, 2, 5 };
        int amount = 5;
        System.out.println(change(amount, coins));
    }
}

4

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1                      # one way to make 0

    for coin in coins:            # coins on the outside
        for a in range(coin, amount + 1):   # low to high
            dp[a] += dp[a - coin]
    return dp[amount]


coins = [1, 2, 5]
amount = 5
print(change(amount, coins))

4

function change(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;                        // one way to make 0

  for (const coin of coins) {       // coins on the outside
    for (let a = coin; a <= amount; a++) {  // low to high
      dp[a] += dp[a - coin];
    }
  }
  return dp[amount];
}

const coins = [1, 2, 5];
const amount = 5;
console.log(change(amount, coins));

4

Let us walk through the Python version line by line. The why behind each line is what keeps the count correct.

dp = [0] * (amount + 1) makes one row of counts, all zero. dp[a] will mean “ways to make amount a”. We start with no known ways.

dp[0] = 1 is the seed. There is exactly one way to make zero, which is to use no coins. Every other count grows out of this one.

for coin in coins: puts the coins on the outside. This is the key choice. By fixing one coin fully before moving to the next, we count each combination once. So 1 + 2 and 2 + 1 never both appear.

for a in range(coin, amount + 1): walks amounts from the coin value up to the target, low to high. Low to high is correct here because each coin can repeat. We want the current coin’s earlier results to feed into later amounts.

dp[a] += dp[a - coin] is the transition. The ways to make a grow by the ways to make a - coin, since adding one more of this coin turns those into ways to make a. We add, not replace, because we keep the ways that did not use this coin too.

return dp[amount] gives the answer. After all coins, this slot holds the total number of combinations.

⏱️ Time and Space Complexity

Plain recursion is exponential, since it re-solves the same coin and amount pairs. Memoization and 2D tabulation both visit each coin and amount pair once, so they run in O(coins times amount) time. The space-optimized version keeps one array, so it uses O(amount) memory while staying just as fast.

🧩 Key Takeaways

• ✅ We count combinations, so order does not matter.
• ✅ Each coin can repeat, which makes this an unbounded knapsack.
• ✅ There is one way to make amount zero, which seeds the table.
• ✅ Loop coins on the outside to count combinations, not arrangements.
• ✅ One rolling array of size amount plus one is enough.

🚀 What’s Next?

• Partition Equal Subset Sum
• Best Time to Buy and Sell Stock with Cooldown