Bird
Raised Fist0

Identify the subtle bug that causes incorrect results on some inputs: ```python def subset_sum(nums, S): dp = [False] * (S + 1) dp[0] = True for num in nums: for w in range(num, S + 1): # forward iteration dp[w] = dp[w] or dp[w - num] return dp[S] ```

medium🐞 Bug Identification Q7 of Q15
Dynamic Programming: Knapsack - Subset Sum
The following code attempts to solve subset sum using space-optimized DP. Identify the subtle bug that causes incorrect results on some inputs: ```python def subset_sum(nums, S): dp = [False] * (S + 1) dp[0] = True for num in nums: for w in range(num, S + 1): # forward iteration dp[w] = dp[w] or dp[w - num] return dp[S] ```
AMissing base case for target zero in recursion
BIterating sums forwards causes reuse of updated dp values, leading to overcounting
CUsing dp array of size S+1 instead of n+1
DNot initializing dp[0] to True
Step-by-Step Solution
Solution:
  1. Step 1: Understand iteration direction

    Forward iteration updates dp[w] using dp[w - num] which may have been updated in the same iteration.
  2. Step 2: Identify consequence

    This causes counting the same element multiple times, invalid for 0/1 subset sum.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Backward iteration prevents reuse of updated dp values [OK]
Quick Trick: Iterate sums backward to avoid reuse in 0/1 knapsack [OK]
Common Mistakes:
MISTAKES
  • Forward iteration seems intuitive
  • Ignoring update order effects
Trap Explanation:
PITFALL
  • Candidates often overlook iteration direction causing subtle bugs.
Interviewer Note:
CONTEXT
  • Tests candidate's understanding of DP update order and correctness.
Master "Subset Sum" 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