The following code attempts to solve the subset sum problem using space-optimized DP. Identify the bug that causes incorrect results on some inputs.

medium🐞 Bug Identification Q14 of Q15

Dynamic Programming: Knapsack - Subset Sum

ALine 2: dp[0] should be initialized to False

BLine 6: dp[w] should be assigned dp[w - num] only, not ORed

CLine 4: The outer loop should iterate backwards over nums

DLine 5: The inner loop iterates forwards instead of backwards

Step-by-Step Solution

Solution:

Step 1: Understand dp update direction
Iterating forwards causes dp[w] to use updated dp[w - num] from the same iteration, leading to overcounting.
Step 2: Correct iteration direction
Iterating backwards ensures dp[w - num] is from previous iteration, preserving correctness.
Final Answer:
Option D -> Option D
Quick Check:
Forward iteration breaks subset sum correctness -> bug at line 5 [OK]

Quick Trick: DP must iterate sums backward to avoid reuse in same iteration [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Forward iteration looks natural but breaks correctness subtly, passing some tests.

Interviewer Note:

CONTEXT

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

More Dynamic Programming: Knapsack Quizzes