Target Sum

▶

Steps

setup

Calculate total sum and offset

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.

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. 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

1. 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.

2. 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.

3. Final Answer:

   Option B -> Option B

4. 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 count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?

medium

A. Line 5: inner loop iterating backwards over amounts

B. Line 4: outer loop over coins

C. Line 2: dp initialization

D. Line 6: updating dp[w] with dp[w - coin]

Solution

1. Step 1: Understand iteration order effect

   Iterating amounts backwards causes dp to count permutations, not combinations.

2. Step 2: Identify bug line

   Line 5 iterates w from amount down to coin, which breaks combination counting logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration over amounts is required to count combinations correctly [OK]

Hint: Check direction of inner loop iteration [OK]

Common Mistakes:

• Using backward iteration in 1D dp
• Misplacing dp[0] initialization

3. Identify the bug in the following code snippet for counting ways to make change using 1D DP:

def count_ways_bug(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for w in range(amount, coin - 1, -1):
            dp[w] += dp[w - coin]
    return dp[amount]

What is the bug?

medium

A. dp[0] should be initialized to 1, not 0

B. The inner loop should iterate forwards from coin to amount, not backwards

C. The dp array size should be amount, not amount + 1

D. The return statement should return dp[0] instead of dp[amount]

Solution

1. Step 1: Check base case initialization

   dp[0] represents ways to make amount 0, which must be 1 (empty combination), but here it is set to 0, causing all dp values to remain 0.

2. Step 2: Verify loop direction

   Though iterating backwards is incorrect for unlimited coin usage, the critical bug causing zero results is dp[0] initialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct base case dp[0]=1 is essential for counting ways [OK]

Hint: dp[0] must be 1 to count empty combination [OK]

Common Mistakes:

• Initializing dp[0] to 0 misses base case
• Iterating amounts backwards in 1D DP misses combinations
• Incorrect dp array size causes index errors

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

1. 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.

2. 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.

3. Final Answer:

   Option A -> Option A

4. 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 integer break problem is modified so that you can reuse the same integer parts multiple times (unbounded splits), and you want to find the maximum product. Which modification to the DP approach below correctly handles this variant?

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

Options:

hard

A. Use a nested loop where for each i, iterate j from 1 to i and update dp[i] = max(dp[i], j * dp[i-j]) to allow reuse

B. Sort possible parts and greedily pick the largest part repeatedly to maximize product

C. Keep the same code but add memoization to avoid recomputation

D. Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j])

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means dp[i] depends on dp[i-j] multiplied by j (or dp[j]) where j can be reused multiple times.

2. Step 2: Modify DP update

   Updating dp[i] = max(dp[i], j * dp[i-j]) correctly models unbounded splits by combining current part j and best product for remaining i-j.

3. Step 3: Evaluate other options

   Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j]) removes max(j, dp[j]) incorrectly; Keep the same code but add memoization to avoid recomputation adds memoization but doesn't change logic; Sort possible parts and greedily pick the largest part repeatedly to maximize product is greedy and fails on some inputs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Unbounded knapsack style DP uses dp[i] = max(dp[i], j * dp[i-j]) [OK]

Hint: Unbounded knapsack uses dp[i] = max(dp[i], j * dp[i-j]) [OK]

Common Mistakes:

• Using greedy approach
• Not adjusting DP recurrence for reuse