The O(n) Club: Coin Change 2: Counting Combos, Not Coins (Because Life’s Complicated Enough)

The O(n) Club: Coin Change 2 — Counting Combos, Not Coins (Because Life’s Complicated Enough)

⚡ TL;DR

Count the number of ways to make a given amount using unlimited coins of each denomination. Don’t brute force like you’re counting coins under your couch—use DP, like a grownup Java dev:

// Java: Counting coin combinations the clean way
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];

🧠 How Devs Usually Mess This Up

Ah, rookie mistake #37: thinking [1,2] and [2,1] are different. If you count permutations, your output will be as wrong as putting pineapple on pizza (sorry, Hawaii). People also confuse this with Coin Change 1, which wants the minimum coins, not the number of ways. Don’t mix up your greedy algorithms here: your interviewer will notice, and they’ll love pointing it out.

🔍 What’s Actually Going On

Picture you’re building the world’s sweetest coffee: you have unlimited scoops of three sugars. Your goal? Hit exactly 10 sweet units. Does it matter if you added vanilla first or coconut second? Nope. It just matters how many of each scoop you grabbed. We’re counting combinations, not barista style points. To avoid double-counting combos, run your loop over coin types first. Each new coin “unlocks” more combos for later amounts—no duplicates, no nonsense.

🛠️ PseudoCode

• Start with an array dp of size amount+1. Set dp[0] = 1 (because doing nothing is technically one way).
• Loop through each coin:
• For every total from coin up to amount:
• Update dp[total] += dp[total - coin]
• Return dp[amount] at the end; that’s your answer.

// Pseudo-Java for your next whiteboard
int[] dp = new int[amount + 1];
dp[0] = 1;
for each coin in coins:
    for i = coin to amount:
        dp[i] += dp[i - coin];

💻 The Code

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];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Order matters for sandwiches, not change: outer loop must be coin. Reverse it, and enjoy famous permutation failures.
• Unlimited coins! This isn’t a museum, you can use each denomination as often as you like.
• Base cases: amount == 0 is 1 way—grab nothing and look proud. Negative amounts or no coins? Not happening: 0 ways.
• Complexity: O(amount × coins) time, O(amount) space. No server will cry.

🧠 Interviewer Brain-Tattoo

“Don’t care how you build your coffee, just count the ways to hit that target buzz—permutations not invited.”