Coin Change II

Coin Change II

What is this problem about?

The Coin Change II interview question is a classic variation of the original Coin Change problem. Instead of finding the minimum number of coins, you need to find the total number of unique combinations that make up a target amount. You are given an array of coin denominations and an infinite supply of each. This problem emphasizes counting distinct sets rather than permutations.

Why is this asked in interviews?

Amazon, Google, and Bloomberg frequently use the Coin Change II coding problem to test a candidate's grasp of Dynamic Programming (DP) and specifically their ability to avoid double-counting. It’s a subtle but critical distinction between "how many ways to reach a sum" and "how many unique combinations exist." Interviewers want to see if you can manipulate the order of loops to achieve the correct counting logic.

Algorithmic pattern used

The problem uses Bottom-Up Dynamic Programming. The key to counting unique combinations (and avoiding permutations) is the order of the nested loops. You must iterate through the coins first and then the amounts.

• dp[i] stores the number of ways to make amount i.
• For each coin:
  • For each amount from coin to target:
    • dp[amount] += dp[amount - coin]

Example explanation

Coins: [1, 2], Amount: 4

1. Initialize dp[0] = 1, all other dp values to 0.
2. Process coin 1:
   • dp[1] += dp[0] = 1
   • dp[2] += dp[1] = 1
   • dp[3] += dp[2] = 1
   • dp[4] += dp[3] = 1
   • dp array: [1, 1, 1, 1, 1]
3. Process coin 2:
   • dp[2] += dp[0] = 2 (Ways: {1,1}, {2})
   • dp[3] += dp[1] = 2 (Ways: {1,1,1}, {1,2})
   • dp[4] += dp[2] = 3 (Ways: {1,1,1,1}, {1,1,2}, {2,2}) Result: 3.

Common mistakes candidates make

• Loop Order: Swapping the loops (amount first, then coins) results in counting permutations (e.g., {1, 2} and {2, 1} are counted as two different ways).
• Initialization: Forgetting to set dp[0] = 1 (there is exactly one way to make an amount of 0: using no coins).
• Space Complexity: Using a 2D DP table when a 1D array is sufficient, which might be flagged as inefficient in memory-constrained environments.

Interview preparation tip

Always clarify if the interviewer wants "combinations" (order doesn't matter) or "permutations" (order matters). This distinction completely changes the loop structure of your DP solution.