We compute the total sum of nums (5) and set offset to this total to handle negative sums by shifting indices.
💡 Offsetting indices allows us to use a 1D array to represent sums from -total to +total as valid indices.
Line:total = sum(nums)
offset = total
💡 Indexing sums with offset simplifies handling negative sums in the dp array.
setup
Initialize dp array with base case
Initialize dp array of size 11 (2*total+1) with all zeros except dp[offset] = 1, representing one way to reach sum 0.
💡 Setting dp[offset] = 1 means there is exactly one way to reach sum zero before processing any numbers.
Line:dp = [0] * (2 * total + 1)
dp[offset] = 1
💡 Base case initialization is crucial for building up counts of sums.
fill_row
Process first number (1), initialize next_dp
Start processing the first number 1. Initialize next_dp array with zeros to store updated counts.
💡 We use next_dp to avoid overwriting dp while iterating sums.
Line:for num in nums:
next_dp = [0] * (2 * total + 1)
💡 Using a separate array for updates preserves previous state during iteration.
fill_cells
Update next_dp for sum +1 from dp[offset]
For sum index 5 (offset), dp[5] = 1 means one way to reach sum 0. Add this count to next_dp[5 + 1] = next_dp[6].
💡 Adding the current number increases the sum by 1, so ways to reach sum 1 increase.
Line:if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s]
💡 This step shows how adding the current number updates ways to reach higher sums.
fill_cells
Update next_dp for sum -1 from dp[offset]
From dp[5] = 1, also add this count to next_dp[5 - 1] = next_dp[4], representing subtracting the current number.
💡 Subtracting the current number decreases the sum by 1, increasing ways to reach sum -1.
Line:if dp[s] != 0:
if s - num >= 0:
next_dp[s - num] += dp[s]
💡 This step shows how subtracting the current number updates ways to reach lower sums.
fill_row
Finish processing first number, update dp
After processing all sums for the first number, assign dp = next_dp to update the dp array.
💡 Updating dp prepares for the next number's processing with new counts.
Line:dp = next_dp
💡 dp now reflects ways to reach sums after including the first number.
fill_row
Process second number (1), initialize next_dp
Start processing the second number 1. Initialize next_dp with zeros again.
💡 We repeat the update process for the next number.
Line:for num in nums:
next_dp = [0] * (2 * total + 1)
💡 Each number updates dp based on previous counts.
fill_cells
Update next_dp for sum +1 from dp[4]
From dp[4] = 1 (sum -1), add count to next_dp[4 + 1] = next_dp[5], representing sum 0 after adding current number.
💡 Adding current number shifts sums right by 1.
Line:if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s]
💡 Ways to reach sum 0 increase by ways to reach sum -1 previously.
fill_cells
Update next_dp for sum -1 from dp[4]
From dp[4] = 1, add count to next_dp[4 - 1] = next_dp[3], representing sum -2 after subtracting current number.
💡 Subtracting current number shifts sums left by 1.
Line:if dp[s] != 0:
if s - num >= 0:
next_dp[s - num] += dp[s]
💡 Ways to reach sum -2 increase accordingly.
fill_cells
Update next_dp for sum +1 from dp[6]
From dp[6] = 1 (sum 1), add count to next_dp[6 + 1] = next_dp[7], sum 2 after adding current number.
💡 Adding current number shifts sums right by 1.
Line:if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s]
💡 Ways to reach sum 2 increase.
fill_cells
Update next_dp for sum -1 from dp[6]
From dp[6] = 1, add count to next_dp[6 - 1] = next_dp[5], sum 0 after subtracting current number.
💡 Subtracting current number shifts sums left by 1.
Line:if dp[s] != 0:
if s - num >= 0:
next_dp[s - num] += dp[s]
💡 Ways to reach sum 0 increase further.
fill_row
Finish processing second number, update dp
Assign dp = next_dp after processing second number to update counts.
💡 dp now reflects ways to reach sums after two numbers.
Line:dp = next_dp
💡 dp array grows with counts of ways to reach sums.
fill_row
Process third number (1), initialize next_dp
Initialize next_dp with zeros to process the third number 1.
💡 We continue updating dp for each number.
Line:for num in nums:
next_dp = [0] * (2 * total + 1)
💡 Each iteration builds on previous dp.
fill_cells
Update next_dp for sum +1 from dp[3]
From dp[3] = 1 (sum -2), add count to next_dp[4] (sum -1) by adding current number.
💡 Adding current number shifts sums right.
Line:if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s]
💡 Ways to reach sum -1 increase.
fill_cells
Update next_dp for sum -1 from dp[3]
From dp[3] = 1, add count to next_dp[2] (sum -3) by subtracting current number.
💡 Subtracting current number shifts sums left.
Line:if dp[s] != 0:
if s - num >= 0:
next_dp[s - num] += dp[s]
💡 Ways to reach sum -3 increase.
fill_cells
Update next_dp for sum +1 from dp[5]
From dp[5] = 2 (sum 0), add count to next_dp[6] (sum 1) by adding current number.
💡 Adding current number shifts sums right.
Line:if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s]
💡 Ways to reach sum 1 increase by 2.
fill_cells
Update next_dp for sum -1 from dp[5]
From dp[5] = 2, add count to next_dp[4] (sum -1) by subtracting current number.
💡 Subtracting current number shifts sums left.
Line:if dp[s] != 0:
if s - num >= 0:
next_dp[s - num] += dp[s]
💡 Ways to reach sum -1 increase by 2.
fill_cells
Update next_dp for sum +1 from dp[7]
From dp[7] = 1 (sum 2), add count to next_dp[8] (sum 3) by adding current number.
💡 Adding current number shifts sums right.
Line:if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s]
💡 Ways to reach sum 3 increase.
fill_cells
Update next_dp for sum -1 from dp[7]
From dp[7] = 1, add count to next_dp[6] (sum 1) by subtracting current number.
💡 Subtracting current number shifts sums left.
Line:if dp[s] != 0:
if s - num >= 0:
next_dp[s - num] += dp[s]
💡 Ways to reach sum 1 increase by 1.
fill_row
Finish processing third number, update dp
Assign dp = next_dp after processing third number to update counts.
💡 dp now reflects ways to reach sums after three numbers.
Line:dp = next_dp
💡 dp array grows with counts of ways to reach sums.
fill_row
Process fourth number (1), initialize next_dp
Initialize next_dp with zeros to process the fourth number 1.
💡 Continue updating dp for each number.
Line:for num in nums:
next_dp = [0] * (2 * total + 1)
💡 Each iteration builds on previous dp.
fill_row
Process fifth number (1), initialize next_dp
Initialize next_dp with zeros to process the fifth number 1.
💡 Continue updating dp for the last number.
Line:for num in nums:
next_dp = [0] * (2 * total + 1)
💡 Final iteration to build dp.
fill_row
Final dp array after processing all numbers
After processing all numbers, dp array holds counts of ways to reach each sum. The answer is dp[target + offset] = dp[3 + 5] = dp[8] = 5.
💡 The dp array now contains the total ways to reach every sum from -5 to 5.
Line:return dp[target + offset] if -total <= target <= total else 0
💡 The final answer is the count of ways to reach the target sum.
def findTargetSumWays(nums, target):
total = sum(nums) # STEP 1
offset = total # STEP 1
dp = [0] * (2 * total + 1) # STEP 2
dp[offset] = 1 # STEP 2
for i, num in enumerate(nums): # STEP 3,7,13,21,22
next_dp = [0] * (2 * total + 1) # STEP 3,7,13,21,22
for s in range(2 * total + 1):
if dp[s] != 0:
if s + num <= 2 * total:
next_dp[s + num] += dp[s] # STEP 4,8,10,14,16,18,20...
if s - num >= 0:
next_dp[s - num] += dp[s] # STEP 5,9,11,15,17,19,21...
dp = next_dp # STEP 6,12,20,23
return dp[target + offset] if -total <= target <= total else 0 # STEP 23
if __name__ == '__main__':
print(findTargetSumWays([1,1,1,1,1], 3)) # Output: 5
📊
Target Sum - Watch the Algorithm Execute, Step by Step
Watching the dp array update step-by-step reveals how the algorithm counts combinations of plus and minus assignments to reach the target sum.
Step 1/23
·Active fill★Answer cell
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
?
?
?
?
?
?
?
?
?
?
?
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
0
1
0
0
0
0
0
dp[offset]=1
Item 0 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
0
1
0
0
0
0
0
dp[offset]=1
Item 0 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
0
0
1
0
0
0
0
dp[5]=1
Item 0 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
1
0
1
0
0
0
0
dp[5]=1
Item 0 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
1
0
1
0
0
0
0
dp[4]=1
Item 1 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
1
0
1
0
0
0
0
dp[4]=1
Item 1 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
0
1
0
0
0
0
0
dp[4]=1
Item 1 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
1
0
1
0
0
0
0
0
dp[4]=1
Item 1 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
1
0
1
0
1
0
0
0
dp[6]=1
Item 1 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
1
0
2
0
1
0
0
0
dp[6]=1
Item 1 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
1
0
2
0
1
0
0
0
dp[3]=1
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
1
0
2
0
1
0
0
0
dp[3]=1
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
0
0
1
0
0
0
0
0
0
dp[3]=1
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
1
0
0
0
0
0
0
dp[3]=1
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
1
0
2
0
0
0
0
dp[5]=2
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
3
0
2
0
0
0
0
dp[5]=2
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
3
0
2
0
1
0
0
dp[7]=1
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
3
0
3
0
1
0
0
dp[7]=1
Item 2 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
3
0
3
0
1
0
0
dp[2]=1
Item 3 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
3
0
3
0
1
0
0
dp[2]=1
Item 4 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
3
0
3
0
1
0
0
dp[2]=1
Item 4 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
i=0
0
0
1
0
4
0
6
0
5
0
0
Answer dp[8]=5
Key Takeaways
✓ Offsetting indices allows handling negative sums in a single dp array.
This trick is not obvious from code alone but is crucial for indexing sums from -total to +total.
✓ Using a separate next_dp array prevents overwriting dp during iteration, preserving previous state.
This ensures correct accumulation of counts without losing data mid-iteration.
✓ Each dp cell accumulates counts of ways to reach a sum by adding or subtracting the current number.
Watching how counts shift left and right in dp clarifies how sums evolve step-by-step.
Practice
(1/5)
1. Consider the following code for computing the minimum number of perfect squares summing to n. What is the value of dp[4] after the outer loop iteration i = 4 completes?
easy
A. 4
B. 1
C. 3
D. 2
Solution
Step 1: Trace dp[4] updates
For i=4, j iterates over 1 and 2 because 1*1=1 <=4 and 2*2=4 <=4.
- For j=1: dp[4] = min(inf, 1 + dp[3]) = 1 + dp[3]
- For j=2: dp[4] = min(previous, 1 + dp[0]) = min(previous, 1 + 0) = 1
Since dp[0] = 0, dp[4] becomes 1.
Step 2: Confirm dp[4] final value
dp[4] = 1 means 4 can be represented as one perfect square (2*2). This matches the expected minimal count.
Final Answer:
Option B -> Option B
Quick Check:
dp[4] = 1 for 4 = 2^2 [OK]
Hint: dp[4] = 1 because 4 is a perfect square itself [OK]
Common Mistakes:
Off-by-one errors in loop
Ignoring dp[0] base case
2. The following code attempts to implement the space-optimized 0/1 Knapsack solution. Identify the line that contains a subtle bug that can cause incorrect results.
def knapsack_space_optimized(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(weights[i], W + 1): # Note: iterating forwards
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
medium
A. Line 5: Inner loop iterating forwards over weights.
B. Line 4: Outer loop iterating over items.
C. Line 2: Initializing dp array with zeros.
D. Line 6: Updating dp[w] with max of current and new value.
Solution
Step 1: Analyze iteration order in inner loop
The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.
Step 2: Correct iteration direction
Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.
Final Answer:
Option A -> Option A
Quick Check:
Forward iteration causes overcounting items [OK]
Hint: Inner loop must iterate backwards to avoid overcounting [OK]
Common Mistakes:
Iterating forwards in dp array updates for 0/1 knapsack.
3. What is the time complexity of the DP with bitmask tabulation approach for partitioning an array of size n into k equal sum subsets, where the algorithm iterates over all subsets and elements?
medium
A. O(k^n) because it tries all assignments of elements to k buckets
B. O(n * 2^n) because it iterates over all subsets and elements
C. O(n * target) where target is the subset sum
D. O(2^n * n^2) due to nested loops over subsets and elements
Solution
Step 1: Identify loops in the algorithm
The outer loop iterates over all subsets (2^n), inner loop over n elements.
Step 2: Calculate total complexity
Combining loops gives O(n * 2^n). The target sum does not affect iteration count directly.
Final Answer:
Option A -> Option A
Quick Check:
DP bitmask iterates all subsets and elements [OK]
Hint: Bitmask DP complexity is n times 2^n subsets [OK]
Common Mistakes:
Confusing brute force backtracking complexity with DP complexity
Assuming complexity depends on target sum
4. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?
medium
A. Line 3: Missing base case assignment dp[0] = 0
B. Line 2: dp initialization with infinity
C. Line 5: Outer loop from 1 to n
D. Line 7: Inner loop condition j*j <= i
Solution
Step 1: Identify base case importance
dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.
Step 2: Analyze impact of missing dp[0] = 0
Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.
Final Answer:
Option A -> Option A
Quick Check:
Missing dp[0] base case breaks DP initialization [OK]
Hint: dp[0] must be zero to start DP correctly [OK]
Common Mistakes:
Forgetting dp[0] initialization
Misplacing loop boundaries
5. Suppose the problem is modified so that each string can be chosen multiple times (unbounded usage). Which change to the dynamic programming approach correctly adapts the solution?
hard
A. Iterate dp array forwards to allow multiple counts of the same string
B. Iterate dp array backwards as before to avoid counting duplicates
C. Use recursion without memoization to handle repeated choices
D. Increase dp dimensions to track usage count of each string
Solution
Step 1: Understand difference between 0/1 and unbounded knapsack
Unbounded knapsack allows multiple uses of the same item, so dp updates must allow reuse within the same iteration.
Step 2: Adjust dp iteration order
Iterating dp forwards enables using updated states multiple times, correctly counting repeated strings.
Step 3: Confirm correctness
Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded usage.