Bird
Raised Fist0

Identify the bug: ```python def min_subset_sum_diff(arr): total_sum = sum(arr) dp = [False] * (total_sum + 1) for num in arr: for w in range(num, total_sum + 1): dp[w] = dp[w] or dp[w - num] half = total_sum // 2 for w in range(half, -1, -1): if dp[w]: return total_sum - 2 * w ```

medium🐞 Bug Identification Q7 of Q15
Dynamic Programming: Knapsack - Minimum Subset Sum Difference
The following code attempts to solve the minimum subset sum difference problem using space-optimized DP. Identify the bug: ```python def min_subset_sum_diff(arr): total_sum = sum(arr) dp = [False] * (total_sum + 1) for num in arr: for w in range(num, total_sum + 1): dp[w] = dp[w] or dp[w - num] half = total_sum // 2 for w in range(half, -1, -1): if dp[w]: return total_sum - 2 * w ```
AThe outer loop should iterate backwards over arr
Bdp[0] is not initialized to True before loops
CThe inner loop should iterate from 0 to total_sum
DThe final loop should start from total_sum instead of half
Step-by-Step Solution
Solution:
  1. Step 1: Check dp initialization

    dp[0] must be True to represent sum 0 achievable initially; missing here.
  2. Step 2: Analyze iteration order

    Inner loop iterates forward, which can cause overcounting, but main bug is dp[0] initialization.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Without dp[0]=True, no sums are achievable -> wrong output [OK]
Quick Trick: dp[0] must be True to start subset sum DP [OK]
Common Mistakes:
MISTAKES
  • Forgetting dp[0] initialization
  • Forward iteration causing overcounting
Trap Explanation:
PITFALL
  • Candidates focus on loop direction but miss dp[0] initialization, which breaks correctness.
Interviewer Note:
CONTEXT
  • Tests subtle DP initialization bugs that cause silent failures.
Master "Minimum Subset Sum Difference" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Dynamic Programming: Knapsack Quizzes