Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogle

Coin Change II (Count Ways)

Choose your preparation mode4 modes available
</>
IDE
def change(amount: int, coins: list[int]) -> int:public int change(int amount, int[] coins)int change(int amount, vector<int>& coins)function change(amount, coins)
def change(amount, coins):
    # Write your solution here
    pass
class Solution {
    public int change(int amount, int[] coins) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int change(int amount, vector<int>& coins) {
    // Write your solution here
    return 0;
}
function change(amount, coins) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: Counting permutations instead of combinations (too large count)Looping amounts outer and coins inner, causing order-sensitive counting.✅ Change loop order: iterate coins outer loop, amounts inner loop to count combinations.
Wrong: Zero ways returned for amount=0Not initializing dp[0] = 1 to represent empty combination.✅ Initialize dp[0] = 1 before DP iteration.
Wrong: Non-zero ways returned when coins array is emptyNot handling empty coins input properly.✅ Return 0 for any positive amount if coins array is empty.
Wrong: Treating problem as 0/1 knapsack limiting coin usage to onceIncorrect DP update disallowing multiple usage of same coin.✅ Allow unlimited usage by updating dp in coin outer loop and amounts inner loop.
Wrong: TLE on large inputsUsing brute force recursion or exponential approach.✅ Implement bottom-up DP with O(n*amount) time complexity.
✓
Test Cases
t1_01basic
Input{"amount":5,"coins":[1,2,5]}
Expected4

The four combinations are: 5=5; 5=2+2+1; 5=2+1+1+1; 5=1+1+1+1+1 (order does not matter).

t1_02basic
Input{"amount":3,"coins":[2]}
Expected0

No combination of coin 2 can make amount 3.

t2_01edge
Input{"amount":0,"coins":[1,2]}
Expected1

Only one way to make amount 0: use no coins (empty combination).

t2_02edge
Input{"amount":3,"coins":[]}
Expected0

No coins means no way to form any positive amount.

t2_03edge
Input{"amount":10,"coins":[10]}
Expected1

Only one combination: using the single coin once to make amount 10.

t2_04edge
Input{"amount":7,"coins":[2,4]}
Expected0

No combination of 2 and 4 can make 7.

t3_01corner
Input{"amount":5,"coins":[1,3,4]}
Expected3

Combinations: 1+1+1+1+1, 1+1+3, 1+4, 3+3 is invalid (exceeds amount). Valid are 4 combinations total.

t3_02corner
Input{"amount":4,"coins":[1,2]}
Expected3

Combinations: 1+1+1+1, 1+1+2, 2+2

t3_03corner
Input{"amount":7,"coins":[2,4]}
Expected0

No combination of 2 and 4 can make 7.

t4_01performance
Input{"amount":10000,"coins":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}
⏱ Performance - must finish in 2000ms

Large input with n=100 coins and amount=10000; O(n*amount) DP must complete within 2s.

Practice

(1/5)
1. Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?
def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))
easy
A. 240
B. 180
C. 160
D. 220

Solution

  1. Step 1: Trace dp array updates for each item

    For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.
  2. Step 2: Final dp[50] value

    The maximum value achievable with capacity 50 is 220.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Manual dp tracing confirms max value 220 [OK]
Hint: Trace dp updates backward to avoid overcounting [OK]
Common Mistakes:
  • Forwards iteration over w causes overcounting items.
2. The following code attempts to solve the coin change minimum coins problem. Identify the line containing the subtle bug that causes incorrect results or infinite recursion for amount=0.
def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        res = float('inf')
        for coin in coins:
            if rem - coin >= 0:
                res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1
medium
A. Line 3: Missing base case for rem < 0
B. Line 6: Missing check for rem == 0 before recursion
C. Line 9: Returning res without checking if res is still infinity
D. Line 7: Incorrect condition rem - coin >= 0 instead of rem >= coin

Solution

  1. Step 1: Analyze base cases in recursion

    Code handles rem == 0 but lacks base case for rem < 0, but since rem - coin >= 0 check prevents negative rem, no infinite recursion occurs.
  2. Step 2: Check return value correctness

    Returning res directly without checking if res is still infinity can cause incorrect results when no valid coin combination exists.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Must check if res is infinity before returning to handle no solution cases correctly [OK]
Hint: Check if result is infinity before returning in recursion [OK]
Common Mistakes:
  • Forgetting to handle no solution case
  • Assuming rem == 0 base case suffices
3. The following code attempts to solve the Equal Partition problem using a 1D DP array. Which line contains a subtle bug that can cause incorrect results on some inputs?
def canPartition(nums):
    total = sum(nums)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(num, target + 1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]
medium
A. Line 2: Missing check if total is even before proceeding
B. Line 4: Initializing dp array with false instead of true
C. Line 6: Iterating forwards in dp array instead of backwards
D. Line 8: Returning dp[target] without verifying dp array correctness

Solution

  1. Step 1: Identify missing even check

    Line 2 does not check if total is even, but this causes no incorrect dp updates, only wasted computation.
  2. Step 2: Analyze dp iteration direction

    Line 6 iterates forwards, which causes reuse of updated dp values in the same iteration, leading to counting elements multiple times and incorrect results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Backward iteration is required to avoid reusing updated dp values in the same iteration [OK]
Hint: DP must iterate backwards to avoid reuse in 1D array [OK]
Common Mistakes:
  • Iterating forwards in dp updates
  • Skipping even sum check
4. What is the time complexity of the bottom-up dynamic programming solution for the Perfect Squares problem using the unbounded knapsack pattern, where n is the input number?
medium
A. O(n^2)
B. O(sqrt(n) * log n)
C. O(n * log n)
D. O(n * sqrt(n))

Solution

  1. Step 1: Identify loops in the algorithm

    The outer loop runs from 1 to n (O(n)). The inner loop iterates over all perfect squares less than or equal to i, which is approximately O(sqrt(n)) because the largest square root is about sqrt(n).
  2. Step 2: Combine complexities

    Multiplying outer and inner loops gives O(n * sqrt(n)). Other options either overestimate (O(n^2)) or underestimate (O(n log n), O(sqrt(n) log n)) the complexity.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Nested loops: n and sqrt(n) -> O(n * sqrt(n)) [OK]
Hint: Inner loop runs up to sqrt(n), outer up to n [OK]
Common Mistakes:
  • Assuming inner loop is O(n)
  • Confusing recursion stack space with DP space
5. Suppose the problem is modified so that each string can be chosen multiple times (unbounded usage). Which change to the dynamic programming approach correctly adapts the solution?
hard
A. Iterate dp array forwards to allow multiple counts of the same string
B. Iterate dp array backwards as before to avoid counting duplicates
C. Use recursion without memoization to handle repeated choices
D. Increase dp dimensions to track usage count of each string

Solution

  1. Step 1: Understand difference between 0/1 and unbounded knapsack

    Unbounded knapsack allows multiple uses of the same item, so dp updates must allow reuse within the same iteration.
  2. Step 2: Adjust dp iteration order

    Iterating dp forwards enables using updated states multiple times, correctly counting repeated strings.
  3. Step 3: Confirm correctness

    Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded usage.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Forward iteration enables multiple item usage [OK]
Hint: Unbounded knapsack uses forward dp iteration [OK]
Common Mistakes:
  • Continuing backward iteration from 0/1 knapsack
  • Adding extra dp dimensions unnecessarily
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard