Target Sum

📋

Problem

Imagine you have a list of numbers and want to assign '+' or '-' signs to each so that the total equals a target sum. How many ways can you do this?

Given an array of integers nums and an integer target, return the number of different expressions that can be built by adding '+' or '-' before each integer such that the resulting expression evaluates to target. Input: nums (list of integers), target (integer) Output: integer representing the count of valid expressions.

1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 10000 ≤ sum(nums[i]) ≤ 1000-1000 ≤ target ≤ 1000

Edge cases: nums = [0,0,0,0,0], target = 0 → 32 (all combinations of + and - count)nums = [1000], target = 1000 → 1 (only +1000 works)nums = [1], target = 2 → 0 (no way to reach 2)

</>

IDE

def findTargetSumWays(nums: list[int], target: int) -> int:public int findTargetSumWays(int[] nums, int target)int findTargetSumWays(vector<int>& nums, int target)function findTargetSumWays(nums, target)

def findTargetSumWays(nums, target):
    # Write your solution here
    pass

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findTargetSumWays(vector<int>& nums, int target) {
    // Write your solution here
    return 0;
}

function findTargetSumWays(nums, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Base case returns 0 instead of 1 when index == len(nums) and current sum == target.✅ Change base case to return 1 if current sum equals target at recursion end.

Wrong: 1Ignoring sign assignments for zeros, counting only one way instead of 2^count_of_zeros.✅ Branch on both + and - for zeros as well to count all combinations.

Wrong: Nonzero for impossible targetIncorrect base case or pruning allowing invalid sums to count.✅ Return 0 when sums do not match target at recursion end.

Wrong: Wrong count due to greedy approachGreedy sign assignment misses multiple valid ways.✅ Use DP or recursion to enumerate all sign assignments.

Wrong: TLEUsing brute force recursion without memoization for large n.✅ Implement memoization or bottom-up DP to reduce complexity to O(n*sum).

✓

Test Cases

Focus on handling base cases like empty arrays and zeros correctly.

Consider common algorithmic pitfalls like greedy traps and usage constraints.

Think about time complexity and how to optimize exponential recursion with DP.

t1_01basic

Input{"nums":[1,1,1,1,1],"target":3}

Expected5

⏱ Performance - must finish in 2000ms

There are 5 ways to assign signs to get sum 3: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1.

💡 Think about how to explore all combinations of + and - signs for each number.

💡 Use recursion or dynamic programming to count ways to reach target sums at each step.

💡 Use a DP table or memoization to store counts of sums achievable with subsets of nums.

Why it failed: Incorrect count indicates missing some sign combinations or incorrect base case. Fix by ensuring base case returns 1 only when current sum equals target at end of recursion.

✓ Correctly counts all valid sign assignments matching target sum.

t1_02basic

Input{"nums":[2,3,1],"target":2}

Expected1

⏱ Performance - must finish in 2000ms

Only one way: -2+3+1=2. Other sign combinations do not yield target 2.

💡 Try enumerating all sign assignments for small arrays to verify counts.

💡 Check if your solution correctly handles sums that can be formed by different sign patterns.

💡 Ensure your DP or recursion counts all valid paths without skipping any.

Why it failed: Wrong output means some sign combinations are missed or double counted. Fix by correctly branching on both + and - for each element.

✓ Correctly enumerates all sign assignments and counts those matching target.

t2_01edge

Input{"nums":[],"target":0}

Expected1

⏱ Performance - must finish in 2000ms

Empty array with target 0 counts as one valid expression (empty sum).

💡 Consider the base case when no numbers are left to assign signs.

💡 The empty expression should count as one way if target is zero.

💡 Return 1 if index reaches length and current sum equals target, else 0.

Why it failed: Returning 0 for empty input misses the empty expression case. Fix by returning 1 when index == len(nums) and current sum == target.

✓ Correctly counts empty expression as one valid way when target is zero.

t2_02edge

Input{"nums":[0,0,0,0,0],"target":0}

Expected32

⏱ Performance - must finish in 2000ms

Each zero can be +0 or -0, doubling ways each time: 2^5=32 ways.

💡 Zeros do not change sum but affect count of expressions.

💡 Each zero doubles the number of ways to reach the same sum.

💡 Ensure your DP or recursion counts all sign assignments even if sum unchanged.

Why it failed: Ignoring zeros or treating them as one way causes undercount. Fix by branching on both + and - for zeros as well.

✓ Correctly counts all 2^n sign assignments including zeros.

t2_03edge

Input{"nums":[1000],"target":1000}

Expected1

⏱ Performance - must finish in 2000ms

Only +1000 matches target 1000; -1000 does not.

💡 Check sign assignments for single element arrays.

💡 Only one sign may produce the target sum.

💡 Return 1 if nums[0] == target or -nums[0] == target, else 0.

Why it failed: Counting both + and - signs without checking sum causes wrong count. Fix by verifying sum equals target at base case.

✓ Correctly counts single element sign assignments matching target.

t3_01corner

Input{"nums":[1,2,3],"target":7}

Expected0

⏱ Performance - must finish in 2000ms

Target 7 cannot be formed by any combination of + or - signs on [1,2,3].

💡 Check if your solution correctly returns zero when no expressions match target.

💡 Verify base case returns 0 when current sum != target at end.

💡 Ensure no false positives from partial sums exceeding target.

Why it failed: Returning nonzero count for impossible target means base case or pruning is incorrect. Fix by returning 0 when sums don't match at recursion end.

✓ Correctly returns zero when no valid expressions exist.

t3_02corner

Input{"nums":[1,1,1,1,1],"target":1}

Expected10

⏱ Performance - must finish in 2000ms

Multiple ways to assign signs to get sum 1, similar to canonical example but different target.

💡 Beware of greedy approaches that pick signs to maximize sum without counting all ways.

💡 Use DP or recursion to explore all sign assignments exhaustively.

💡 Count all valid paths, not just one maximal or minimal sum.

Why it failed: Greedy or partial sum approaches miss multiple valid ways. Fix by enumerating all sign assignments via DP or recursion.

✓ Correctly counts all valid sign assignments for target 1.

t3_03corner

Input{"nums":[1,2,3,4],"target":0}

Expected2

⏱ Performance - must finish in 2000ms

No combination of + or - signs on [1,2,3,4] sums to 0.

💡 Check that your solution distinguishes 0/1 knapsack from unbounded knapsack.

💡 Each number can be used exactly once with + or - sign.

💡 Avoid counting repeated use of same element multiple times.

Why it failed: Counting unbounded usage of elements inflates count. Fix by ensuring each element is used exactly once in recursion or DP.

✓ Correctly counts ways respecting 0/1 usage constraint.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10],"target":10}

Expectednull

⏱ Performance - must finish in 2000ms

n=20, sum(nums)=110, DP O(n*sum) ~ 2200 operations must complete within 2s.

💡 Brute force recursion is O(2^n) and will time out for n=20.

💡 Use memoization or bottom-up DP to achieve O(n*sum(nums)) time.

💡 Store intermediate results to avoid recomputation of subproblems.

Why it failed: TLE indicates exponential brute force used. Fix by implementing memoization or DP to reduce complexity to O(n*sum).

✓ Efficient DP or memoized recursion runs within time limit.

Practice

1. Given the following code, what is the output when coins = [1, 2, 5] and amount = 5?

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

coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))

easy

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Trace dp array updates for each coin

   Start dp = [1,0,0,0,0,0]. After coin=1, dp = [1,1,1,1,1,1]. After coin=2, dp = [1,1,2,2,3,3]. After coin=5, dp = [1,1,2,2,3,6].

2. Step 2: Confirm dp[5] value

   dp[5] = 6, representing 6 ways to make amount 5 with coins [1,2,5].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual dp tracing matches output 6 [OK]

Hint: DP accumulates counts incrementally per coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Miscounting after last coin iteration
• Confusing permutations with combinations

2. Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with nums = [1, 2, 3, 4] and k = 2?

from typing import List

def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                if dp[next_mask] == -1:
                    dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target

   Sum is 10, k=2, target subset sum = 5.

2. Step 2: Trace dp updates

   DP explores subsets; for example, {1,4} and {2,3} both sum to 5, so dp[(1<<4)-1] = 0, returning True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Partition exists: [1,4] and [2,3] [OK]

Hint: Sum divisible by k and dp final state 0 means partition possible [OK]

Common Mistakes:

• Confusing dp array indexing or bitmask operations
• Forgetting to check if largest element exceeds target

3. What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?

medium

A. O(2^n)

B. O(n + W)

C. O(n * W)

D. O(n * log W)

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.

2. Step 2: Calculate total operations

   Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n and W -> O(n * W) [OK]

Hint: Nested loops over items and capacity -> O(n * W) [OK]

Common Mistakes:

• Confusing recursion stack space with time complexity.

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for counting the number of ways to make change with n coins and amount W?

medium

A. O(n * W) because for each coin we iterate over all amounts up to W

B. O(n + W) because we iterate over coins and amounts separately

C. O(W^n) due to nested loops over coins and amounts

D. O(n * W) plus O(W) auxiliary space for the dp array

Solution

1. Step 1: Identify loops and their ranges

   Outer loop runs n times (coins), inner loop runs up to W (amount), so time is O(n * W).

2. Step 2: Consider space usage

   DP array size is W+1, so auxiliary space is O(W). Total complexity includes both time and space, but time complexity is the main focus here.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time O(n*W) matches DP approach [OK]

Hint: Time is product of coins and amount; space is dp array size [OK]

Common Mistakes:

• Confusing time with space complexity
• Forgetting auxiliary space for dp array
• Mistaking exponential complexity for DP

5. Examine the following code snippet which attempts to solve the problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: zeros = s.count('0')

B. Line 10: for j in range(0, n - ones + 1):

C. Line 9: for i in range(0, m - zeros + 1): # iterating forwards

D. Line 11: dp[i + zeros][j + ones] = max(dp[i + zeros][j + ones], 1 + dp[i][j])

Solution

1. Step 1: Understand dp iteration direction

   To avoid counting the same string multiple times, dp must be updated backwards (from high to low indices).

2. Step 2: Identify bug in iteration

   Iterating forwards over i and j causes dp states to be reused within the same iteration, leading to overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backward iteration is required for 0/1 knapsack variants [OK]

Hint: Forward iteration in 0/1 knapsack dp causes double counting [OK]

Common Mistakes:

• Forgetting to iterate dp backwards
• Miscounting zeros and ones