Target Sum

Target Sum

What is this problem about?

In the Target Sum coding problem, you are given an array of integers and a target value. For each integer in the array, you must assign either a + or a - sign to it. Your goal is to find the number of ways to assign these signs such that the total sum of the expression equals the target. For example, if the array is [1, 1, 1, 1, 1] and the target is 3, one way is +1+1+1+1-1 = 3.

Why is this asked in interviews?

This is a classic "Medium" problem asked by many companies, including Apple, Meta, and Google. It can be approached using recursion (backtracking) or optimized using dynamic programming. It tests whether you can identify overlapping subproblems and if you can reduce the problem to a more standard one, like the "Subset Sum" problem. It evaluates your ability to handle recursive complexity and memory optimization.

Algorithmic pattern used

The primary patterns are Backtracking and Dynamic Programming.

1. Backtracking: Explore all 2^n combinations by recursively adding or subtracting each number. This is slow for large n.
2. DP (Subset Sum reduction): Let P be the sum of positive numbers and N be the sum of negative numbers.
   • P - N = target
   • P + N = total_sum
   • 2P = target + total_sum => P = (target + total_sum) / 2. The problem becomes finding the number of subsets that sum up to P. This is the standard 0/1 Knapsack / Subset Sum pattern.

Example explanation

Array: [2, 1], Target: 1.

• Total Sum = 3.
• We need P = (1 + 3) / 2 = 2.
• How many subsets sum to 2?
  • {2} is one subset.
• There is 1 way. Check: +2 - 1 = 1. (Correct!) If the target was 3: P = (3+3)/2 = 3. Subset {2, 1} sums to 3. 1 way. (+2+1=3)

Common mistakes candidates make

One frequent mistake is using simple recursion without memoization, leading to an exponential time complexity that fails for arrays longer than 20-30 elements. Another error is not checking the edge cases where (target + total_sum) is odd or where the target is greater than the total possible sum; in these cases, the answer is always zero. Candidates also sometimes struggle with the mathematical derivation that leads to the Subset Sum reduction.

Interview preparation tip

When studying for the Target Sum interview question, master the Backtracking interview pattern with memoization first. Then, learn how to convert it to the Dynamic Programming interview pattern (specifically the 0/1 Knapsack variant). Understanding the relationship between partition problems and target sums is key for solving many variation questions in technical interviews.