0

Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?

easy🧾 Code Trace Q12 of Q15

Dynamic Programming: Knapsack - Target Sum

Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?

A1

B3

C0

D2

Step-by-Step Solution

Step 1: Trace initial dp array
total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)
Step 2: Process num=1 and num=2 updating dp
After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.
Final Answer:
Option D -> Option D
Quick Check:
Two ways: +1-2 and -1+2 sum to 1 [OK]

Quick Trick: Offset indexing maps sums to dp indices [OK]

Common Mistakes:

MISTAKES

Off-by-one errors in indexing dp array

Trap Explanation:

PITFALL

Forgetting offset or miscalculating dp indices leads to wrong counts.

Interviewer Note:

CONTEXT

Tests candidate's ability to mentally execute DP with offset indexing.

Master "Target Sum" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Dynamic Programming: Knapsack Quizzes