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.
Step 3: Find largest w ≤ half with dp[w] = true
dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
Final Answer:
Option B -> Option B
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. What is the time complexity of the optimal bottom-up dynamic programming solution for the Coin Change II problem with n coins and target amount amount?
medium
A. O(amount^2)
B. O(n + amount)
C. O(2^amount)
D. O(n * amount)
Solution
Step 1: Identify loops in code
Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.
Step 2: Calculate complexity
Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).
Final Answer:
Option D -> Option D
Quick Check:
Nested loops over coins and amounts confirm O(n * amount) [OK]
Hint: Count nested loops and their ranges [OK]
Common Mistakes:
Confusing amount with n
Forgetting recursion stack space
Assuming quadratic in amount
3. The following code attempts to solve the minimum subset sum difference problem using space-optimized DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 4: dp initialization without dp[0] = true
B. Line 6: Outer loop iterating over elements
C. Line 7: Inner loop iterating backwards from total_sum
D. Line 11: Returning difference using total_sum and w
Solution
Step 1: Check base case initialization
dp[0] must be true to represent sum zero achievable with empty subset; missing this causes no sums to be marked achievable.
Step 2: Verify other lines
Loops and return statement are correct; only missing dp[0] initialization breaks correctness.
Final Answer:
Option A -> Option A
Quick Check:
Without dp[0] = true, dp array never updates correctly [OK]
Hint: dp[0] = true is essential base case [OK]
Common Mistakes:
Forgetting dp[0] initialization
Using forward iteration causing overcounting
4. 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
Step 1: Understand unlimited reuse impact
Allowing multiple uses of the same job means the problem resembles unbounded interval scheduling with no overlaps.
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).
Final Answer:
Option B -> Option B
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
5. Suppose the problem is modified so that each element in the array can be chosen multiple times (unbounded). Which modification to the DP approach correctly solves this variant?
hard
A. Change inner loop to iterate forwards from num to total_sum to allow reuse
B. Keep inner loop iterating backwards from total_sum to num as in original code
C. Use recursion without memoization to handle multiple uses
D. Sort array and greedily pick largest elements repeatedly
Solution
Step 1: Understand reuse impact on DP iteration
For unbounded knapsack variants, inner loop must iterate forwards to allow multiple counts of the same element.
Step 2: Contrast with original code
Original code iterates backwards to avoid counting elements multiple times; forward iteration enables reuse.
Final Answer:
Option A -> Option A
Quick Check:
Forward iteration in inner loop enables multiple uses of elements [OK]
Hint: Forward iteration allows multiple element reuse in DP [OK]
Common Mistakes:
Using backward iteration causing single use only
Assuming recursion without memo is efficient
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.