Target Sum

medium2D Dynamic Programming68 stepsJava · Python · C++

Assign + or − to every number so the total equals target; count the ways. If P is the sum of the + numbers, then P − (total − P) = target, so P = (total + target) / 2. Count subsets with that sum.

▶ Watch the animated trace

Traced input: nums = [1, 1, 1, 1, 1], target = 3 → 5. Original problem: neetcode.io/problems/target-sum

Complexity

BestO(n·S)

AverageO(n·S)

WorstO(n·S)

SpaceO(S)

S = (total + target) / 2.

Key idea

Rewriting the signs as a subset sum turns it into a counting knapsack.
If total + target is odd or |target| > total, the answer is 0.
Iterate sums downward so each number is used once.
Zeros double the count (±0 are different assignments); the DP handles that.

Common mistakes

Brute-force recursion is O(2ⁿ).
Forgetting the parity and range checks.
Negative target: use abs(target) in the range check.

Solution

Java

int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;
    if (Math.abs(target) > total || (total + target) % 2 != 0) {
        return 0;
    }
    int want = (total + target) / 2;
    int[] dp = new int[want + 1];
    dp[0] = 1;
    for (int i = 0; i < nums.length; i++) {
        for (int s = want; s >= nums[i]; s--) {
            dp[s] += dp[s - nums[i]];
        }
    }
    return dp[want];
}

Python

def findTargetSumWays(nums: List[int], target: int) -> int:
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0
    want = (total + target) // 2
    dp = [1] + [0] * want
    for x in nums:
        for s in range(want, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[want]

C++

int findTargetSumWays(vector<int>& nums, int target) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (abs(target) > total || (total + target) % 2 != 0) {
        return 0;
    }
    int want = (total + target) / 2;
    vector<int> dp(want + 1);
    dp[0] = 1;
    for (int x : nums) {
        for (int s = want; s >= x; s--) {
            dp[s] += dp[s - x];
        }
    }
    return dp[want];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single number +1.	`nums = [1], target = 1`	`1`
Unreachable \|4\| > total 3.	`nums = [1, 2], target = 4`	`0`
Zeros Each 0 can be +0 or −0: 2 × 2 = 4 ways.	`nums = [0, 0, 1], target = 1`	`4`
Negative target Only −1 + 2 − 3 = −2.	`nums = [1, 2, 3], target = -2`	`1`