Coin Change II

Problem Link

Problem Statement

Given an integer amount and an array coins of distinct integers representing coin denominations, return the number of combinations that make up that amount.
You may use unlimited coins of any denomination.

Intuition

This is a counting problem, not about the minimum number of coins.
Each coin can be used unlimited times.
Order does not matter (combinations, not permutations).
It's a classic Unbounded Knapsack variation where the goal is to count the number of ways to reach the target sum using the given coin denominations.

Step 1: Recursion (Pick / Not Pick with IBH)

IBH Format

Induction: count(i, amount) → number of combinations to make up amount using first i+1 coins.
Base Case:
- If i == 0:
  - If amount % coins[0] == 0 → return 1 (only 1 way)
  - Else → return 0
Hypothesis: Subproblem solutions give correct results.
Induction Step:
- Not Pick: go to i-1
- Pick: stay on i, reduce amount

Java Code: Recursion

class Solution {
    public int change(int amount, int[] coins) {
        return count(coins.length - 1, amount, coins);
    }

    private int count(int i, int amount, int[] coins) {
        if (i == 0) {
            return (amount % coins[0] == 0) ? 1 : 0;
        }

        int notPick = count(i - 1, amount, coins);
        int pick = 0;
        if (coins[i] <= amount) {
            pick = count(i, amount - coins[i], coins);
        }

        return pick + notPick;
    }
}

Time Complexity: Exponential O(2^n)
Space Complexity: O(amount) (recursion stack)

Step 2: Memoization (Top-Down DP)

Java Code: Memoization

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        Integer[][] dp = new Integer[n][amount + 1];
        return count(n - 1, amount, coins, dp);
    }

    private int count(int i, int amount, int[] coins, Integer[][] dp) {
        if (i == 0) {
            return (amount % coins[0] == 0) ? 1 : 0;
        }

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

        int notPick = count(i - 1, amount, coins, dp);
        int pick = 0;
        if (coins[i] <= amount) {
            pick = count(i, amount - coins[i], coins, dp);
        }

        return dp[i][amount] = pick + notPick;
    }
}

Time Complexity: O(n * amount)
Space Complexity: O(n * amount) (memo table) + O(amount) (recursion stack)

Step 3: Tabulation (Bottom-Up DP)

Java Code

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

        // Base case: only use coins[0]
        for (int amt = 0; amt <= amount; amt++) {
            dp[0][amt] = (amt % coins[0] == 0) ? 1 : 0;
        }

        for (int i = 1; i < n; i++) {
            for (int amt = 0; amt <= amount; amt++) {
                int notPick = dp[i - 1][amt];
                int pick = 0;
                if (coins[i] <= amt) {
                    pick = dp[i][amt - coins[i]];
                }
                dp[i][amt] = pick + notPick;
            }
        }

        return dp[n - 1][amount];
    }
}

Time Complexity: O(n * amount)
Space Complexity: O(n * amount)

Step 4: Space Optimization (2 Rows → 1 Row)

Java Code: Optimized

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

        // Base case
        for (int amt = 0; amt <= amount; amt++) {
            prev[amt] = (amt % coins[0] == 0) ? 1 : 0;
        }

        for (int i = 1; i < n; i++) {
            int[] curr = new int[amount + 1];
            for (int amt = 0; amt <= amount; amt++) {
                int notPick = prev[amt];
                int pick = 0;
                if (coins[i] <= amt) {
                    pick = curr[amt - coins[i]];
                }
                curr[amt] = pick + notPick;
            }
            prev = curr;
        }

        return prev[amount];
    }
}

Time Complexity: O(n * amount)
Space Complexity: O(amount)

Choice Diagram

                      count(i, amount)
                      /            \
             notPick                pick
        count(i - 1, amount)   count(i, amount - coins[i])

Final Notes

This problem models combinations (not permutations).
Ideal for mastering unbounded knapsack pattern.
Space optimization can reduce from 2D to 1D DP effectively.