Target Sum

1 day ago
5 min read

Target Sum is about counting how many ways I can reach a goal by making binary choices over a sequence. That makes it a great interview question for testing dynamic programming instincts.

Problem Statement

You are given an integer array nums and an integer target.

You can assign either a + or - sign to each number in nums.

Return the number of different expressions that evaluate to target.

1. Clarify Requirements Before Jumping Into Code

Before I code, I lock down what’s being asked.

Input:
- nums: array of integers
- target: integer
Output: number of valid expressions
Each number must be used exactly once
Order stays fixed; only the sign changes

Questions I mentally check:

Can numbers be zero? Yes, and that matters.
Can the target be negative? Yes.
Do I need to return the expressions themselves? No, just the count.

2. Identify the Category of the Question

We're seeing some of the hallmarks of a Dynamic Programming problem in this question. The first is that we potentially have many possible solutions. While we may not be looking to "optimize" a solution like we've seen in previous DP problems, counting possible solutions is also a form of DP.

We also see some overlapping subproblems - the number of possible solutions to sum up to the larger target sums is going to build on the number of ways to reach smaller target sums.

3. Consider a Brute-Force Approach to Understand the Problem

For the brute-force solution, we simply try every possible sign assignment.

For each number:

Choose + or -

That creates 2ⁿ possible expressions.

Time complexity: O(2ⁿ)
Space complexity: O(n) for recursion

This works for small inputs and helps me see the structure, but it won’t scale.

4. Brainstorm More Solutions

Let's take a step back and try to reframe the problem. One idea is to see if we can formalize our parameters into some kind of mathematical formula.

We essentially have two categories of numbers here: those I have added and those I have subtracted. So first, let's think about our numbers as two sets:

Numbers I add → set P
Numbers I subtract → set N

What do we know about these two sets? We know that together they should add up to our target:

sum(P) - sum(N) = target

Now, what else do we know about our parameters? Are there any variables we haven't used yet?

Yes, there is: we can quite easily determine the totalSum of our input array - the sum of all the elements in nums. How do we put together an equation using totalSum?

sum(P) + sum(N) = totalSum

Notice that we have some common variables in both these equations. That means we can manipulate our equations to try and isolate one of our variables.

Which variable do we isolate? Well, since ultimately we want to identify our two sums, that's what we should solve for:

2 * sum(P) = target + totalSum

sum(P) = (target + totalSum) / 2

With this simplified equation, we can simplify our coding problem - instead of having to manage two variables (P and N), we can instead focus on one.

And with that, the question we to answer becomes: How many subsets of nums add up to sum(P)?

We can take a moment here to see if there are any obvious insights based purely on our equation.

The first insight is that since we are dividing by 2 in our equation, target + totalSum cannot be odd, since our target is an integer, and dividing an odd number by 2 will not result in an integer.

We also know that target + totalSum cannot be negative. There's no way to achieve a negative result when all of your numbers are positive.

So the solution in both of these cases is 0.

Alright, so now we know what we're working towards: sum(P), i.e. (target + totalSum) / 2. We can name that variable targetSum.

Now let's try applying the standard DP approach to solving that problem.

First, we'll start by creating a DP array dp where each element represents the number of ways to reach sum(i). The size of this array is targetSum + 1, because I only care about sums from 0 up to targetSum.

Next, consider the base case. All we really know at the beginning is that there’s exactly one way to make a sum of 0: choose nothing. So let's initialize our dp array with:

dp[0] = 1

Everything else starts at 0.

Now we can start processing each number in the nums array. For each num, we need to update all of the elements in our DP array that could use the current num as one potential solution to reach sum(i).

Should we fill in our dp array from left to right or right to left? We have to go backwards because we don’t want to reuse the same number multiple times in a single iteration. Each number should only contribute once per layer of the DP.

So for each index i from targetSum down to num, we update:

dp[i] += dp[i - num]

This line is the heart of the algorithm.

It means: the number of ways to reach dp(i) includes all the ways we could previously reach dp(i - num), plus the current solutions.

As we iterate through all the numbers, the DP array gradually accumulates the count of all valid subset combinations.

By the time we finish processing the entire array, dp[targetSum] contains exactly what we want: the number of ways to form the required subset sum, which corresponds to the number of ways to reach the original target in the Target Sum problem.

Time Complexity: O(n × targetSum)

Space Complexity: O(targetSum).

That’s a big improvement over the exponential brute-force recursion, and it scales well enough for typical interview constraints.

Final approach recap:

Compute totalSum of the array.
Compute targetSum = (target + totalSum) / 2.
Run the counting DP.
Return dp[targetSum].

5. Discuss Trade-Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute force	O(2ⁿ)	O(n)	Simple to reason about	Too slow
Subset sum reduction	O(n × targetSum)	O(targetSum)	Clean, efficient	Requires algebra insight

6. Write Pseudocode to Structure Your Thoughts

totalSum = sum(nums)
if (target + totalSum) is odd or < 0:
    return 0

targetSum = (target + totalSum) / 2
dp[0] = 1

for each num in nums:
    for i from targetSum down to num:
        dp[i] += dp[i - num]

return dp[targetSum]

7. Consider Edge Cases

nums contains zeros → doubles counts
target outside possible sum range
Empty array
Single-element array

The DP naturally handles these when initialized correctly.

8. Write Full Code Syntax

public class TargetSum {

    public static int findTargetSumWays(int[] nums, int target) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if ((target + totalSum) % 2 != 0 || Math.abs(target) > totalSum) {
            return 0;
        }

        int targetSum = (target + totalSum) / 2;
        int[] dp = new int[targetSum + 1];
        dp[0] = 1;

        for (int num : nums) {
            for (int i = targetSum; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }

        return dp[targetSum];
    }
}

9. Test Your Code

System.out.println(findTargetSumWays(new int[]{1,1,1,1,1}, 3)); // 5
System.out.println(findTargetSumWays(new int[]{1}, 1));        // 1
System.out.println(findTargetSumWays(new int[]{1}, 2));        // 0
System.out.println(findTargetSumWays(new int[]{0,0,0,0}, 0));  // 16
System.out.println(findTargetSumWays(new int[]{2,3,5}, 10));   // 0

These tests cover:

Standard examples
Impossible targets
Zero-heavy inputs
Boundary conditions

10. Key Lessons to Remember for Future Questions

Algebraic transformations can dramatically simplify DP.
Know whether you’re counting ways or checking feasibility.
Be careful to avoid reusing inputs when considering which direction you should process your data

Target Sum rewards candidates who slow down and reframe the problem before coding. That habit pays off far beyond this question.

Good Luck and Happy Coding!