Dynamic Programming: Knapsack - Target Sum
What is the time complexity of the space-optimized bottom-up DP solution for the Target Sum problem with input array length n and total sum S = sum(nums)?
What is the time complexity of the space-optimized bottom-up DP solution for the Target Sum problem with input array length n and total sum S = sum(nums)?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Step 1: Identify loops in the DP
The outer loop runs n times, the inner loop runs over sums from -S to S, total 2S+1 states.Step 2: Calculate total operations
Each iteration updates dp for each sum, so total time is O(n * S). Exponential 2^n is brute force, not DP.Final Answer:
Option B -> Option BQuick Check:
DP complexity depends on n and sum range, not exponential [OK]
Quick Trick: DP iterates over n and sum range, not all subsets [OK]
Common Mistakes:
MISTAKES- Confusing brute force 2^n with DP complexity
Trap Explanation:
PITFALL- 2^n looks plausible but DP prunes redundant states; n^2 or n log S are incorrect interpretations of loops.
Interviewer Note:
CONTEXT- Checks if candidate understands DP complexity vs brute force.
Master "Target Sum" in Dynamic Programming: Knapsack
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Dynamic Programming: Knapsack Quizzes