Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Target Sum

Target Sum explained: turn the plus/minus sign problem into counting subsets with a fixed sum, then a 0/1 knapsack DP. Tested Python and an interactive visual.

Also searched as: target sum plus minus signs · assign + and - to reach target · count subsets with given difference

🎒

Try it live Free

0/1 Knapsack (DP)

In the Knapsack lab, watch every cell make a take-or-skip decision from the row above; in Target Sum, "take" means a plus sign and cells add up counts instead of values.

Also useful: Backtracking: Subsets, Permutations & Pruning

Open the playground →

The problem

You are given a list of non-negative integers and a target. Put a + or - sign in front of every number. Count how many sign assignments make the expression equal target.

Inputnums = [1, 1, 1, 1, 1], target = 3
Output5

Exactly one number gets a minus sign, in any of 5 positions.

Inputnums = [1], target = 2
Output0

The key insight

Call the numbers with a plus sign P and the rest N. Then sum(P) - sum(N) = target and sum(P) + sum(N) = total, so sum(P) = (total + target) / 2. The question becomes how many subsets sum to that value, a counting 0/1 knapsack.

Brute force first: Trying both signs for every number gives 2n expressions to evaluate.

Step-by-step approach

  1. Compute total. If |target| > total or total + target is odd, return 0.
  2. Set need = (total + target) // 2.
  3. Create ways of size need + 1 with ways[0] = 1.
  4. For each number x, loop s from need down to x: ways[s] += ways[s - x].
  5. Return ways[need]. Zeros are handled correctly: each zero doubles the count, matching +0 and -0.

Python solution

PYTHON 3tested
def find_target_sum_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0
    need = (total + target) // 2           # sum of the plus-sign group
    ways = [1] + [0] * need
    for x in nums:
        for s in range(need, x - 1, -1):   # downward: each number once
            ways[s] += ways[s - x]
    return ways[need]

Complexity

TimeO(n · S)
SpaceO(S)

One sweep of a table of size about (total + target) / 2 per number.

Common mistakes

Frequently asked questions

What is the time and space complexity of Target Sum?

The subset-sum DP is O(n × S) time and O(S) space, where S is the sum of the numbers. The recursive version with memo on (index, sum) is O(n × total) as well.

Why does Target Sum reduce to subset sum?

Splitting the numbers into a plus group P and a minus group N gives sum(P) - sum(N) = target and sum(P) + sum(N) = total. Adding the two equations fixes sum(P), so you only count subsets with that sum.

How do zeros affect the answer?

Each zero can take either sign without changing the sum, so it doubles the number of ways. The DP naturally handles this if the inner loop includes x = 0.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.