Dynamic Programming: Knapsack - Subset Sum
Given the following space-optimized subset sum code, what is the output when nums = [3, 34, 4, 12, 5, 2] and S = 9?
Given the following space-optimized subset sum code, what is the output when nums = [3, 34, 4, 12, 5, 2] and S = 9?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace dp array updates
Initially dp[0]=True; after processing 3, dp[3]=True; after 4, dp[7]=True; after 5, dp[9]=True.Step 2: Check dp[S]
dp[9] is True, so subset sum 9 is achievable.Final Answer:
Option C -> Option CQuick Check:
Subset [4,3,2] sums to 9 [OK]
Quick Trick: Check dp[S] after processing all nums [OK]
Common Mistakes:
MISTAKES- Forgetting to iterate backwards in dp
- Misindexing dp array
Trap Explanation:
PITFALL- Forward iteration would incorrectly update dp and produce wrong results.
Interviewer Note:
CONTEXT- Tests candidate's ability to mentally execute space-optimized DP code.
Master "Subset Sum" in Dynamic Programming: Knapsack
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Dynamic Programming: Knapsack Quizzes