Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogle

Coin Change II (Count Ways)

Choose your preparation mode4 modes available
🎯
Coin Change II (Count Ways)
mediumDPAmazonGoogle

Imagine you have an unlimited supply of different coin denominations and want to find out how many distinct ways you can make a certain amount. This problem models that real-world scenario of counting combinations.

💡 This is a classic dynamic programming problem where beginners often struggle to understand why greedy approaches fail and how to count combinations without double counting. The challenge is to systematically explore all possibilities efficiently.
📋
Problem Statement

Given an integer amount and a list of distinct coin denominations, return the number of combinations that make up that amount. You may use an unlimited number of coins of each denomination. The order of coins does not matter.

1 ≤ amount ≤ 10^51 ≤ number of coins ≤ 3001 ≤ coin denomination ≤ 10^4
💡
Example
Input"amount = 5, coins = [1, 2, 5]"
Output4

The four combinations are: 5=5; 5=2+2+1; 5=2+1+1+1; 5=1+1+1+1+1

  • amount = 0, coins = [1, 2] → 1 (empty combination)
  • amount = 3, coins = [] → 0 (no coins to form amount)
  • amount = 10, coins = [10] → 1 (only one coin equals amount)
  • amount = 7, coins = [2, 4] → 0 (no combination possible)
🔁
Why DP?
Why greedy fails:

Greedy fails because choosing the largest coin first does not guarantee all combinations are counted. For example, amount=5 with coins=[1,2,5]: greedy picks 5 once, but misses combinations like 2+2+1.

DP state:

dp[i][w] represents the number of ways to make amount w using the first i types of coins.

Recurrence:dp[i][w] = dp[i-1][w] + dp[i][w - coins[i-1]] if w >= coins[i-1], else dp[i-1][w]

Number of ways to make w using first i coins = ways without current coin + ways including current coin (if possible).

⚠️
Common Mistakes
Using greedy approach

Misses valid combinations, returns incorrect count

✅ Use DP to count all combinations systematically

Counting permutations instead of combinations

Overcounts ways, giving wrong answer

✅ Process coins in order and update dp accordingly to avoid duplicates

Not handling base case dp[0] = 1

Results in zero ways for amount zero, breaking DP

✅ Initialize dp[0] = 1 to represent empty combination

Using 1D dp but iterating amounts backwards

Leads to counting permutations, not combinations

✅ Iterate amounts forwards when coins are unlimited

🧠
Brute Force (Pure Recursion)
💡 This approach helps understand the problem's structure by exploring all possible combinations recursively, though it is inefficient.

Intuition

Try every coin at each step and recursively count ways to form the remaining amount until zero or negative.

Algorithm

  1. If amount is 0, return 1 (one valid combination).
  2. If amount is negative or no coins left, return 0 (no valid combination).
  3. Recursively count ways by including the current coin and excluding it.
  4. Sum both counts to get total ways.
💡 The recursion tree grows exponentially because it explores all subsets, making it hard to track without memoization.
Recurrence:countWays(i, amount) = countWays(i+1, amount) + countWays(i, amount - coins[i])
</>
Code
def change(amount, coins):
    def dfs(i, amt):
        if amt == 0:
            return 1
        if amt < 0 or i == len(coins):
            return 0
        return dfs(i + 1, amt) + dfs(i, amt - coins[i])

    return dfs(0, amount)

# Example usage
if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4
Line Notes
def dfs(i, amt):Defines recursive helper to explore coin choices starting at index i
if amt == 0:Base case: exact amount formed means one valid combination
if amt < 0 or i == len(coins):Base case: invalid path if amount negative or no coins left
return dfs(i + 1, amt) + dfs(i, amt - coins[i])Sum ways excluding and including current coin
public class Solution {
    public int change(int amount, int[] coins) {
        return dfs(coins, 0, amount);
    }

    private int dfs(int[] coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.length) return 0;
        return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}
Line Notes
public int change(int amount, int[] coins)Entry point to start recursion
if (amt == 0) return 1;Found a valid combination
if (amt < 0 || i == coins.length) return 0;Invalid path or no coins left
return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);Explore excluding and including current coin
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        return dfs(coins, 0, amount);
    }

private:
    int dfs(vector<int>& coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.size()) return 0;
        return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}
Line Notes
int dfs(vector<int>& coins, int i, int amt)Recursive helper exploring coin choices
if (amt == 0) return 1;Base case: valid combination found
if (amt < 0 || i == coins.size()) return 0;Invalid or no coins left
return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);Sum ways excluding and including coin
function change(amount, coins) {
  function dfs(i, amt) {
    if (amt === 0) return 1;
    if (amt < 0 || i === coins.length) return 0;
    return dfs(i + 1, amt) + dfs(i, amt - coins[i]);
  }
  return dfs(0, amount);
}

// Example usage
console.log(change(5, [1, 2, 5])); // Output: 4
Line Notes
function dfs(i, amt)Recursive function to explore coin combinations
if (amt === 0) return 1;Found a valid way to form amount
if (amt < 0 || i === coins.length) return 0;Invalid path or no coins left
return dfs(i + 1, amt) + dfs(i, amt - coins[i]);Count ways excluding and including current coin
⏱
Complexity
TimeO(2^n) where n is amount, due to exploring all subsets
SpaceO(n) recursion stack depth

Each call branches into two, leading to exponential calls; stack depth is at most amount

💡 For amount=20, this means over a million calls, which is impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠
Top-Down Memoization
💡 Memoization avoids recomputing subproblems by caching results, drastically improving efficiency over brute force.

Intuition

Store results of recursive calls in a table keyed by coin index and remaining amount to reuse them.

Algorithm

  1. Initialize a memo table to store results for each (index, amount) pair.
  2. If amount is 0, return 1.
  3. If amount is negative or no coins left, return 0.
  4. If result is cached, return it.
  5. Otherwise, compute ways by excluding and including current coin, cache and return.
💡 Memoization turns exponential recursion into polynomial by pruning duplicate calls.
Recurrence:dp[i][amt] = dp[i+1][amt] + dp[i][amt - coins[i]]
</>
Code
def change(amount, coins):
    memo = {}
    def dfs(i, amt):
        if amt == 0:
            return 1
        if amt < 0 or i == len(coins):
            return 0
        if (i, amt) in memo:
            return memo[(i, amt)]
        memo[(i, amt)] = dfs(i + 1, amt) + dfs(i, amt - coins[i])
        return memo[(i, amt)]

    return dfs(0, amount)

if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4
Line Notes
memo = {}Cache to store computed results for subproblems
if (i, amt) in memo:Return cached result to avoid recomputation
memo[(i, amt)] = dfs(i + 1, amt) + dfs(i, amt - coins[i])Store computed ways including and excluding coin
return memo[(i, amt)]Return cached or newly computed result
import java.util.*;

public class Solution {
    private Map<String, Integer> memo = new HashMap<>();

    public int change(int amount, int[] coins) {
        return dfs(coins, 0, amount);
    }

    private int dfs(int[] coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.length) return 0;
        String key = i + "," + amt;
        if (memo.containsKey(key)) return memo.get(key);
        int res = dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
        memo.put(key, res);
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}
Line Notes
private Map<String, Integer> memo = new HashMap<>();Memo cache keyed by coin index and amount
String key = i + "," + amt;Create unique key for current subproblem
if (memo.containsKey(key)) return memo.get(key);Return cached result if available
memo.put(key, res);Store computed result to avoid recomputation
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, int> memo;
public:
    int change(int amount, vector<int>& coins) {
        return dfs(coins, 0, amount);
    }

private:
    int dfs(vector<int>& coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.size()) return 0;
        string key = to_string(i) + "," + to_string(amt);
        if (memo.count(key)) return memo[key];
        memo[key] = dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
        return memo[key];
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}
Line Notes
unordered_map<string, int> memo;Cache for storing subproblem results
string key = to_string(i) + "," + to_string(amt);Unique key for memoization
if (memo.count(key)) return memo[key];Return cached result if present
memo[key] = dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);Store computed ways
function change(amount, coins) {
  const memo = new Map();
  function dfs(i, amt) {
    if (amt === 0) return 1;
    if (amt < 0 || i === coins.length) return 0;
    const key = i + ',' + amt;
    if (memo.has(key)) return memo.get(key);
    const res = dfs(i + 1, amt) + dfs(i, amt - coins[i]);
    memo.set(key, res);
    return res;
  }
  return dfs(0, amount);
}

console.log(change(5, [1, 2, 5])); // Output: 4
Line Notes
const memo = new Map();Memo cache to store subproblem results
const key = i + ',' + amt;Unique key for current subproblem
if (memo.has(key)) return memo.get(key);Return cached result if available
memo.set(key, res);Cache computed result for reuse
⏱
Complexity
TimeO(n * amount) where n is number of coins
SpaceO(n * amount) for memo table and recursion stack

Memoization ensures each subproblem computed once; total subproblems = n*amount

💡 For amount=20 and 3 coins, at most 60 subproblems computed, much faster than brute force.
Interview Verdict: Accepted

This approach is efficient enough for most inputs and a good first optimization.

🧠
Bottom-Up Tabulation
💡 Tabulation builds the solution iteratively from smaller subproblems, avoiding recursion and making the process clearer and often faster.

Intuition

Use a 2D dp table where dp[i][w] stores ways to make amount w using first i coins, fill table row by row.

Algorithm

  1. Initialize dp table with dp[0][0] = 1 (one way to make amount 0 with 0 coins).
  2. Iterate over coins (rows) and amounts (columns).
  3. For each cell, ways = ways excluding current coin + ways including current coin if possible.
  4. Return dp[number_of_coins][amount] as final answer.
💡 This approach explicitly shows how subproblems build up to the final solution.
Recurrence:dp[i][w] = dp[i-1][w] + (w >= coins[i-1] ? dp[i][w - coins[i-1]] : 0)
</>
Code
def change(amount, coins):
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):
        for w in range(amount + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= coins[i - 1]:
                dp[i][w] += dp[i][w - coins[i - 1]]

    return dp[n][amount]

if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4
Line Notes
dp = [[0] * (amount + 1) for _ in range(n + 1)]Create 2D DP table for coins and amounts
for i in range(n + 1): dp[i][0] = 1Base case: one way to make amount 0 with any coins
dp[i][w] = dp[i - 1][w]Ways excluding current coin
dp[i][w] += dp[i][w - coins[i - 1]]Add ways including current coin if possible
public class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= amount; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}
Line Notes
int[][] dp = new int[n + 1][amount + 1];2D DP array for subproblems
for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case initialization
dp[i][w] = dp[i - 1][w];Exclude current coin ways
if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Include current coin ways if possible
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= amount; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}
Line Notes
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));Initialize DP table with zeros
for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0
dp[i][w] = dp[i - 1][w];Ways excluding current coin
if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin
function change(amount, coins) {
  const n = coins.length;
  const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));
  for (let i = 0; i <= n; i++) dp[i][0] = 1;

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= amount; w++) {
      dp[i][w] = dp[i - 1][w];
      if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
    }
  }
  return dp[n][amount];
}

console.log(change(5, [1, 2, 5])); // Output: 4
Line Notes
const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));Create 2D DP array initialized to zero
for (let i = 0; i <= n; i++) dp[i][0] = 1;Base case initialization
dp[i][w] = dp[i - 1][w];Exclude current coin ways
if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Include current coin ways if possible
⏱
Complexity
TimeO(n * amount)
SpaceO(n * amount)

We fill a table of size n by amount once, each cell computed in O(1)

💡 For n=3 and amount=5, only 18 cells computed, very efficient.
Interview Verdict: Accepted

This is the standard DP solution for this problem and is interview-ready.

🧠
Space Optimized Bottom-Up DP
💡 We can reduce space from 2D to 1D by iterating amounts in order and updating ways in place, leveraging the unbounded nature of coins.

Intuition

Use a 1D dp array where dp[w] stores ways to make amount w; update dp for each coin by adding ways to make w - coin.

Algorithm

  1. Initialize dp array of size amount+1 with dp[0] = 1.
  2. For each coin, iterate amounts from coin value to amount.
  3. Update dp[w] by adding dp[w - coin] to include new combinations.
  4. Return dp[amount] as the total number of ways.
💡 This approach efficiently accumulates counts without storing full 2D table.
Recurrence:dp[w] += dp[w - coin]
</>
Code
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4
Line Notes
dp = [0] * (amount + 1)Initialize 1D dp array for amounts
dp[0] = 1Base case: one way to make amount 0
for coin in coins:Process each coin one by one
dp[w] += dp[w - coin]Add ways including current coin
public class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int w = coin; w <= amount; w++) {
                dp[w] += dp[w - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}
Line Notes
int[] dp = new int[amount + 1];1D dp array for storing ways
dp[0] = 1;Base case initialization
for (int coin : coins)Iterate over each coin
dp[w] += dp[w - coin];Update ways including current coin
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int w = coin; w <= amount; w++) {
                dp[w] += dp[w - coin];
            }
        }
        return dp[amount];
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}
Line Notes
vector<int> dp(amount + 1, 0);1D dp vector initialized to zero
dp[0] = 1;Base case: one way to make zero amount
for (int coin : coins)Process each coin
dp[w] += dp[w - coin];Add ways including current coin
function change(amount, coins) {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let w = coin; w <= amount; w++) {
      dp[w] += dp[w - coin];
    }
  }
  return dp[amount];
}

console.log(change(5, [1, 2, 5])); // Output: 4
Line Notes
const dp = Array(amount + 1).fill(0);Initialize 1D dp array
dp[0] = 1;Base case initialization
for (const coin of coins)Iterate over coins
dp[w] += dp[w - coin];Update ways including current coin
⏱
Complexity
TimeO(n * amount)
SpaceO(amount)

Single dp array updated for each coin and amount combination

💡 For amount=20 and 3 coins, only 60 updates needed, very space efficient.
Interview Verdict: Accepted

This is the most optimal approach in terms of space and is preferred in interviews.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, coding the space optimized DP is ideal after explaining brute force and memoization briefly.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)N/AMention only - never code
2. Top-Down MemoizationO(n * amount)O(n * amount)No (memo pruning)Yes with extra trackingGood first coding approach
3. Bottom-Up TabulationO(n * amount)O(n * amount)NoYes with extra trackingStandard DP solution
4. Space Optimized DPO(n * amount)O(amount)NoHarder, needs extra bookkeepingBest for final implementation
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show understanding.Introduce memoization to optimize recursion.Present bottom-up tabulation for iterative clarity.Finally, show space optimization for best efficiency.Test code with examples and edge cases.

Time Allocation

Clarify: 2min → Brute Force: 5min → Memoization: 5min → Tabulation: 5min → Space Optimization: 3min → Testing: 5min. Total ~25min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

  • What if order of coins matters? → Use permutations counting approach.
  • How to reconstruct one combination? → Store choices in DP and backtrack.
💡 These follow-ups test deeper understanding of DP variations and solution reconstruction.
🔍
Pattern Recognition

When to Use

1) Problem asks for number of ways/combinations; 2) Unlimited usage of items (coins); 3) Target sum or amount; 4) Order does not matter.

Signature Phrases

number of combinationsunlimited coinsmake up amountorder does not matter

NOT This Pattern When

Problems asking for permutations or limited usage of coins are different patterns.

Similar Problems

Coin Change I - minimum coins neededCombination Sum IV - count permutationsPartition Equal Subset Sum - subset sum problem

Practice

(1/5)
1. You are given a list of jobs where each job has a start time, an end time, and a profit. You want to schedule jobs to maximize total profit such that no two jobs overlap. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming with jobs sorted by end time and binary search to find compatible jobs
B. Pure brute force recursion checking all subsets of jobs
C. Greedy algorithm that always picks the job with the earliest end time
D. Dynamic programming based on sorting jobs by start time and using prefix sums

Solution

  1. Step 1: Understand job scheduling constraints

    The problem requires selecting non-overlapping jobs to maximize profit, which is a classic weighted interval scheduling problem.
  2. Step 2: Identify the optimal approach

    Sorting jobs by end time allows binary searching for the last compatible job, enabling a DP solution that builds optimal profit incrementally.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Greedy fails on overlapping jobs with higher profit; DP with binary search handles all cases optimally [OK]
Hint: Sort by end time and use DP with binary search [OK]
Common Mistakes:
  • Assuming greedy by earliest end time always works
  • Sorting by start time only
  • Trying brute force without pruning
2. Consider the following code snippet implementing the minimum cost for tickets problem. What is the value of dp[0] after the loop completes for the input days = [1,4,6] and costs = [2,7,15]?
easy
A. 6
B. 7
C. 9
D. 4

Solution

  1. Step 1: Trace dp from the end

    dp[3] = 0 (base case). For i=2 (day=6): - 1-day ticket: cost=2 + dp[3]=2 - 7-day ticket: cost=7 + dp[3]=7 - 30-day ticket: cost=15 + dp[3]=15 Minimum = 2 -> dp[2]=2
  2. Step 2: Calculate dp[1] and dp[0]

    i=1 (day=4): - 1-day: cost=2 + dp[2]=4 - 7-day: cost=7 + dp[3]=7 - 30-day: cost=15 + dp[3]=15 Minimum=4 -> dp[1]=4 i=0 (day=1): - 1-day: cost=2 + dp[1]=6 - 7-day: cost=7 + dp[3]=7 - 30-day: cost=15 + dp[3]=15 Minimum=6 -> dp[0]=6
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp[0] correctly computed as 6 [OK]
Hint: Trace dp from end to start carefully [OK]
Common Mistakes:
  • Off-by-one in dp indexing
  • Miscomputing next_i with bisect
  • Confusing costs and dp sums
3. You are given an array of integers and a target integer. You want to assign either a plus or minus sign to each integer such that the resulting sum equals the target. Which algorithmic approach guarantees finding the total number of such assignments efficiently?
easy
A. Sorting the array and using two pointers to find pairs that sum to the target
B. Greedy algorithm that picks signs based on local sum minimization
C. Dynamic programming using a 0/1 knapsack-like approach with state representing achievable sums
D. Divide and conquer by splitting the array and combining results without memoization

Solution

  1. Step 1: Understand problem constraints

    The problem requires counting all sign assignments to reach a target sum, which involves exploring exponential combinations.
  2. Step 2: Identify suitable algorithmic pattern

    Greedy and two-pointer approaches fail because they do not consider all combinations. Divide and conquer without memoization is exponential. DP with states representing achievable sums efficiently counts all valid assignments.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP handles overlapping subproblems and sums efficiently [OK]
Hint: Counting sign assignments requires DP over sums [OK]
Common Mistakes:
  • Thinking greedy or sorting solves counting sign assignments
4. The following code attempts to implement the space-optimized 0/1 Knapsack solution. Identify the line that contains a subtle bug that can cause incorrect results.
def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # Note: iterating forwards
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]
medium
A. Line 5: Inner loop iterating forwards over weights.
B. Line 4: Outer loop iterating over items.
C. Line 2: Initializing dp array with zeros.
D. Line 6: Updating dp[w] with max of current and new value.

Solution

  1. Step 1: Analyze iteration order in inner loop

    The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.
  2. Step 2: Correct iteration direction

    Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration causes overcounting items [OK]
Hint: Inner loop must iterate backwards to avoid overcounting [OK]
Common Mistakes:
  • Iterating forwards in dp array updates for 0/1 knapsack.
5. Suppose the problem is modified so that jobs can be scheduled multiple times (i.e., unlimited reuse of the same job), still without overlapping. Which modification to the optimal DP approach is correct?
hard
A. Replace binary search with linear search to find compatible jobs and keep DP unchanged
B. Use a 1D DP array indexed by time and for each time, consider all jobs that can start then, allowing reuse
C. Keep the same DP with binary search but remove the skip option to always take the current job
D. Sort jobs by start time and use memoized recursion without binary search

Solution

  1. Step 1: Understand unlimited reuse impact

    Allowing multiple uses of the same job means the problem resembles unbounded interval scheduling with no overlaps.
  2. Step 2: Modify DP approach

    Use a 1D DP array indexed by time (e.g., dp[t] = max profit up to time t). For each time, consider all jobs starting at or after t, allowing reuse by updating dp[end_i] = max(dp[end_i], dp[start_i] + profit_i).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search and skip logic do not handle reuse; time-indexed DP handles multiple scheduling [OK]
Hint: Use time-indexed DP for unlimited job reuse [OK]
Common Mistakes:
  • Trying to reuse binary search DP without changes
  • Removing skip option breaks correctness
  • Sorting by start time only
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