Target Sum

Target Sum looks like a math puzzle. You get some numbers and you must put a plus or a minus in front of each one. The interviewer wants to see one thing. Can you count all the ways to reach a target, without trying every combination by brute force? That counting trick is the real test here.

🎯 The Problem

You get some numbers and one target. Here are the rules.

• The array holds non-negative numbers.
• You put either a + or a - sign in front of every number.
• Then you add them all up.
• You return the count of sign choices that reach the target.
• You do not return the signs themselves. Only the count.

For [1, 1, 1, 1, 1] with target 3, one valid way is -1 + 1 + 1 + 1 + 1 = 3. There are more ways too.

Input:  nums = [1, 1, 1, 1, 1], target = 3
Output: 5

Explanation: These five sign choices each reach 3:
  -1 +1 +1 +1 +1 = 3
  +1 -1 +1 +1 +1 = 3
  +1 +1 -1 +1 +1 = 3
  +1 +1 +1 -1 +1 = 3
  +1 +1 +1 +1 -1 = 3

Here is a picture of the choices. At each number you branch into a plus path and a minus path. Every leaf is one full sign choice.

🐢 Approach 1: Try Every Sign (Brute Force)

The idea in one line: try every plus and minus choice and count the ones that hit the target.

The idea:

• Go number by number.
• At each number, branch into two paths. One adds it. One subtracts it.
• At the end of the array, check the running sum.

How it works:

• This is plain recursion. A function that calls itself on a smaller piece.
• The smaller piece is “the rest of the array after this number”.
• If the running sum equals the target at the end, count one.

Why it is weak:

• Every number doubles the number of paths.
• With n numbers you get about 2 to the power n paths.
• Twenty numbers already means over a million paths. Too slow.

Here is the try-every-sign code:

def find_target_sum_ways(nums, target):
    def dfs(index, total):
        if index == len(nums):
            return 1 if total == target else 0
        return dfs(index + 1, total + nums[index]) + dfs(index + 1, total - nums[index])

    return dfs(0, 0)

⚡ Approach 2: Add Memory With Memoization (Better)

The idea in one line: many paths reach the same spot, so save each spot’s answer once.

The idea:

• A “spot” is a current index plus a current running sum.
• Many different paths land on the same (index, sum) spot.
• The answer from that spot never changes.

How it works:

• Memoization saves the answer the first time we reach a spot.
• Next time we reach it, we read the saved answer.
• We store the answer for each (index, sum) pair.
• The sum can be negative, so some languages shift it to stay non-negative.

Why it is faster:

• Each (index, sum) spot is solved once, not over and over.
• The work drops to about the number of distinct spots.

Here is the memoized recursion:

from functools import lru_cache


def find_target_sum_ways(nums, target):
    @lru_cache(None)
    def dfs(index, total):
        if index == len(nums):
            return 1 if total == target else 0
        return dfs(index + 1, total + nums[index]) + dfs(index + 1, total - nums[index])

    return dfs(0, 0)

🚀 Approach 3: Turn It Into Subset Sum (Best)

The idea in one line: split the numbers into a plus group and a minus group, then count subsets.

Here is the clever insight. Split the numbers into two groups. One group P gets a plus sign. The other group N gets a minus sign. Then:

sum(P) - sum(N) = target

Add sum(P) + sum(N) (which is the total of all numbers) to both sides:

2 * sum(P) = target + total
sum(P) = (target + total) / 2

So the question becomes simple.

How it works:

• Count how many subsets add up to (target + total) / 2.
• A subset is some of the numbers chosen out of the array.
• Build a table dp where dp[s] is the number of subsets that sum to s.
• Start with dp[0] = 1. There is one way to make sum zero: pick nothing.
• For each number, update the table from high sums down to low sums.
• Going downward keeps each number used only once.

Why it is fast:

• One table, filled once per number.
• If (target + total) is odd, or target is bigger than total, the answer is 0. No split can work.

Steps to Solve

1. Add up all the numbers to get total.
2. If target + total is odd, return 0. If target is larger than total, return 0.
3. Compute s = (target + total) / 2. This is the subset sum we need to count.
4. Make an array dp of size s + 1, all zeros, and set dp[0] = 1.
5. For each number, loop the sum index from s down to the number. Add dp[index - number] into dp[index].
6. The answer is dp[s].

#include <stdio.h>
#include <stdlib.h>

int findTargetSumWays(int nums[], int n, int target) {
    int total = 0;
    for (int i = 0; i < n; i++) total += nums[i];

    // no split can reach an impossible target
    if (target > total || target < -total) return 0;
    if ((target + total) % 2 != 0) return 0;

    int s = (target + total) / 2;       // subset sum we must count
    int *dp = calloc(s + 1, sizeof(int));
    dp[0] = 1;                          // one way to make sum 0: pick nothing

    for (int i = 0; i < n; i++) {
        for (int j = s; j >= nums[i]; j--) {  // go downward to use each number once
            dp[j] += dp[j - nums[i]];
        }
    }

    int answer = dp[s];
    free(dp);
    return answer;
}

int main(void) {
    int nums[] = {1, 1, 1, 1, 1};
    int target = 3;
    printf("%d\n", findTargetSumWays(nums, 5, target));
    return 0;
}

5

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int findTargetSumWays(vector<int>& nums, int target) {
    int total = 0;
    for (int x : nums) total += x;

    if (target > total || target < -total) return 0;
    if ((target + total) % 2 != 0) return 0;

    int s = (target + total) / 2;          // subset sum to count
    vector<int> dp(s + 1, 0);
    dp[0] = 1;                             // empty subset makes sum 0

    for (int x : nums) {
        for (int j = s; j >= x; j--) {     // downward so x is used once
            dp[j] += dp[j - x];
        }
    }
    return dp[s];
}

int main() {
    vector<int> nums = {1, 1, 1, 1, 1};
    int target = 3;
    cout << findTargetSumWays(nums, target) << endl;
    return 0;
}

5

public class TargetSum {
    public static int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int x : nums) total += x;

        if (target > total || target < -total) return 0;
        if ((target + total) % 2 != 0) return 0;

        int s = (target + total) / 2;        // subset sum to count
        int[] dp = new int[s + 1];
        dp[0] = 1;                           // empty subset makes sum 0

        for (int x : nums) {
            for (int j = s; j >= x; j--) {   // downward so x is used once
                dp[j] += dp[j - x];
            }
        }
        return dp[s];
    }

    public static void main(String[] args) {
        int[] nums = { 1, 1, 1, 1, 1 };
        int target = 3;
        System.out.println(findTargetSumWays(nums, target));
    }
}

5

def find_target_sum_ways(nums, target):
    total = sum(nums)

    # an impossible target or odd split has zero ways
    if abs(target) > total or (target + total) % 2 != 0:
        return 0

    s = (target + total) // 2        # subset sum we must count
    dp = [0] * (s + 1)
    dp[0] = 1                        # one way to make sum 0: pick nothing

    for num in nums:
        for j in range(s, num - 1, -1):   # go downward to use each number once
            dp[j] += dp[j - num]

    return dp[s]


nums = [1, 1, 1, 1, 1]
target = 3
print(find_target_sum_ways(nums, target))

5

function findTargetSumWays(nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);

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

  const s = (target + total) / 2;     // subset sum to count
  const dp = new Array(s + 1).fill(0);
  dp[0] = 1;                          // empty subset makes sum 0

  for (const num of nums) {
    for (let j = s; j >= num; j--) {  // downward so num is used once
      dp[j] += dp[j - num];
    }
  }
  return dp[s];
}

const nums = [1, 1, 1, 1, 1];
const target = 3;
console.log(findTargetSumWays(nums, target));

5

Let us walk through the Python version line by line. This is where the idea clicks.

total = sum(nums)

We add every number up first. We need the total to do the subset-sum math.

if abs(target) > total or (target + total) % 2 != 0:
    return 0

If the target is bigger than the total we can never reach it. And if target + total is odd then (target + total) / 2 is not a whole number. So no subset sum exists. Both cases mean zero ways.

s = (target + total) // 2

This is the magic line. We proved that the count of valid sign choices equals the count of subsets that add up to s. So now we just count subsets.

dp = [0] * (s + 1)
dp[0] = 1

Here dp[j] will hold the number of subsets that add up to j. We start with dp[0] = 1. There is exactly one way to make a sum of zero. Pick no numbers at all.

for num in nums:
    for j in range(s, num - 1, -1):
        dp[j] += dp[j - num]

For each number we update the table. We loop j from s down to num. Going downward matters a lot. It makes sure each number is added to a subset only once. If we went upward we would use the same number many times by mistake. The line dp[j] += dp[j - num] says: every subset that made j - num can now include this number to make j.

return dp[s]

At the end dp[s] holds the count of subsets that reach s. That is our answer.

Below is a picture of the dp table filling up for the subset sum s = 4 on [1, 1, 1, 1, 1]. Each number rolls the counts forward.

⏱️ Time and Space Complexity

The recursion tries every sign, so it is O(2^n) time. Memoization stores each (index, sum) once, so it drops to O(n * sum) time. The subset-sum table is the same order but uses just one row, so its space is small. Here s is the subset sum, which is at most the total of all numbers.

🧩 Key Takeaways

• ✅ A plus and minus choice problem can become a subset-sum counting problem.
• ✅ The needed subset sum is (target + total) / 2. If that is not a whole number, the answer is 0.
• ✅ Set dp[0] = 1, because there is one way to make sum zero: pick nothing.
• ✅ Loop the sum index downward so each number is counted only once.
• ✅ The final answer sits in dp[s], the count of subsets reaching the needed sum.

🚀 What’s Next?

• Interleaving String
• Distinct Subsequences