Subsets & Combinations - Count of Subsets With Sum K
What is the output of the space-optimized DP function for arr = [5] and K = 0?
What is the output of the space-optimized DP function for arr = [5] and K = 0?
medium🧾 Code Trace Q4 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze dp initialization
dp[0] = 1 means empty subset sums to 0.Step 2: Loop behavior when K=0
Inner loop runs from 0 down to num-1=4, which is invalid, so no updates occur.Step 3: Return dp[0]
dp[0] remains 1, so output is 1.Final Answer:
Option B → Option BQuick Check:
Empty subset sums to 0 → count is 1 [OK]
Quick Trick: dp[0] always 1 for empty subset sum [OK]
Common Mistakes:
MISTAKES- Assuming zero subsets if K=0 and ignoring empty subset
Trap Explanation:
PITFALL- Candidates often miss that empty subset counts as one subset summing to zero.
Interviewer Note:
CONTEXT- Tests handling of edge cases with zero target sum and single element.
Master "Count of Subsets With Sum K" in Subsets & Combinations
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Subsets & Combinations Quizzes