Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleFacebook

Subset Sum

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize dp array

Create a dp array of size S+1 (10) initialized to False, then set dp[0] to True because sum 0 is always achievable with no elements.

💡 This initialization sets the base case: sum zero is always possible by choosing no elements.
Line:dp = [False] * (S + 1) dp[0] = True
💡 The dp array tracks which sums are achievable; starting with only sum 0 achievable.
📊
Subset Sum - Watch the Algorithm Execute, Step by Step
Watching the dp array update step-by-step reveals how the algorithm builds solutions from smaller subproblems, making the logic crystal clear.
Step 1/20
·Active fill★Answer cell
Initializing dp array
i\w0123456789
i=0
dp[0] = True (base case)
Item 0 - wt:3 val:3
i\w0123456789
i=0
dp array before processing 3
Item 0 - wt:3 val:3
i\w0123456789
i=0
Check dp[9] = dp[9] or dp[6]
Item 0 - wt:3 val:3
i\w0123456789
i=0
Check dp[8] = dp[8] or dp[5]
Item 0 - wt:3 val:3
i\w0123456789
i=0
Check dp[7] = dp[7] or dp[4]
Item 0 - wt:3 val:3
i\w0123456789
i=0
Check dp[6] = dp[6] or dp[3]
Item 0 - wt:3 val:3
i\w0123456789
i=0
Check dp[5] = dp[5] or dp[2]
Item 0 - wt:3 val:3
i\w0123456789
i=0
Check dp[4] = dp[4] or dp[1]
Item 0 - wt:3 val:3
i\w0123456789
i=0
dp[3] updated to True
Item 1 - wt:34 val:34
i\w0123456789
i=0
No update for 34
Item 2 - wt:4 val:4
i\w0123456789
i=0
dp before processing 4
Item 2 - wt:4 val:4
i\w0123456789
i=0
Check dp[9] = dp[9] or dp[5]
Item 2 - wt:4 val:4
i\w0123456789
i=0
dp[7] updated to True
Item 2 - wt:4 val:4
i\w0123456789
i=0
dp[4] updated to True
Item 3 - wt:12 val:12
i\w0123456789
i=0
No update for 12
Item 4 - wt:5 val:5
i\w0123456789
i=0
dp before processing 5
Item 4 - wt:5 val:5
i\w0123456789
i=0
dp[9] updated to True
Item 4 - wt:5 val:5
i\w0123456789
i=0
dp[8] updated to True
Item 5 - wt:2 val:2
i\w0123456789
i=0
dp before processing 2
Item 5 - wt:2 val:2
i\w0123456789
i=0
dp[6] updated to True

Key Takeaways

✓ The dp array tracks which sums are achievable and updates only from smaller sums to larger sums.

This insight is hard to see from code alone because the backward iteration and boolean logic are subtle.

✓ Numbers larger than the target sum are skipped, showing the algorithm's efficiency in ignoring irrelevant elements.

Seeing this visually clarifies why large numbers don't affect the dp array.

✓ When dp[w] changes from False to True, it means a new sum is achievable by including the current number.

Watching these transitions step-by-step reveals how the solution builds incrementally.

Practice

(1/5)
1. Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
easy
A. 1
B. 0
C. 2
D. 3

Solution

  1. Step 1: Calculate total and half

    Total = 6, half = 3. dp array size = 4, dp[0] = true initially.
  2. Step 2: Update dp for each stone

    For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.
  3. Step 3: Find largest w ≤ half with dp[w] = true

    dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]
Hint: Check dp array for sums up to half total [OK]
Common Mistakes:
  • Returning total instead of minimal difference
  • Off-by-one error in dp indexing
  • Not iterating backwards in dp update
2. Consider the following Python code implementing the optimal job scheduling solution. What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?
easy
A. 120
B. 20
C. 140
D. 100

Solution

  1. Step 1: Sort jobs by end time

    Jobs sorted by end time: [(1,3,20), (2,5,20), (3,10,100)]. Ends = [3,5,10]
  2. Step 2: Calculate dp[2]

    For i=2 (job with start=3, end=10, profit=100): binary search idx = bisect_right(ends, 2) - 1 = 0 (job 0 compatible). take = 100 + dp[0] = 100 + 20 = 120; skip = dp[1] = max profit till job 1 = 20 (from previous iterations). dp[2] = max(120, 20) = 120.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp array after iteration 2 is [20, 20, 120] [OK]
Hint: Binary search finds last compatible job index correctly [OK]
Common Mistakes:
  • Off-by-one in binary search index
  • Using dp[i-1] incorrectly
  • Ignoring base case for dp[0]
3. You need to find the number of distinct ways to make a target amount using unlimited supply of given coin denominations. Which algorithmic approach guarantees counting all unique combinations without overcounting permutations?
easy
A. Greedy algorithm that picks the largest coin first until the amount is reached
B. Dynamic programming using a 1D array iterating coins first, then amounts
C. Backtracking exploring all permutations of coins to sum to the amount
D. Sorting coins and using two pointers to find pairs that sum to the amount

Solution

  1. Step 1: Understand problem constraints

    The problem requires counting unique combinations, not permutations, of coins to reach the target amount.
  2. Step 2: Identify algorithm that counts combinations without duplicates

    Dynamic programming iterating coins first ensures each coin is considered in order, avoiding counting permutations multiple times. The 1D DP approach efficiently accumulates counts for each amount.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP with coin-first iteration counts combinations correctly [OK]
Hint: Coin-first DP avoids permutation overcounting [OK]
Common Mistakes:
  • Using greedy misses some combinations
  • Counting permutations instead of combinations
  • Using two pointers only works for pair sums
4. What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?
medium
A. O(2^n)
B. O(n + W)
C. O(n * W)
D. O(n * log W)

Solution

  1. Step 1: Identify loops in the algorithm

    The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.
  2. Step 2: Calculate total operations

    Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Nested loops over n and W -> O(n * W) [OK]
Hint: Nested loops over items and capacity -> O(n * W) [OK]
Common Mistakes:
  • Confusing recursion stack space with time complexity.
5. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?
hard
A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner
B. Sort coins and greedily pick largest coins without repetition until amount is reached
C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)
D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration

Solution

  1. Step 1: Understand the 0/1 usage constraint

    Each coin can be used once, so we must track usage per coin, requiring 2D dp.
  2. Step 2: Identify correct DP structure

    2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.
  3. Step 3: Why other options fail

    Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    0/1 knapsack requires 2D dp to track coin usage [OK]
Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]
Common Mistakes:
  • Using unbounded knapsack DP for 0/1 problem
  • Assuming greedy works for minimum coins
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