Problem statement

You are given an integer array nums and an integer target. Build an expression by placing a + or - before every number and concatenating them.

Return the number of expressions that evaluate to target.

Example 1

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: Five ways to place signs summing to 3.

Example 2

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

Constraints

• 1 <= nums.length <= 15
• 0 <= nums[i] <= 9
• -20 <= target <= 20

Hints for Target Sum

1. Hint 1

   Track a map from reachable sum → number of ways, one number at a time.

2. Hint 2

   The classic reduction: subset with sum (total+target)/2 — a 0/1 knapsack count.

How to solve Target Sum

Every number gets a sign, so after processing a prefix the only thing that matters is the running total — not which signs produced it. Carry a table mapping each reachable total to the number of ways to reach it, and extend it one number at a time, branching into +x and -x.

Approach

1. Bound the totals: with all values at most 9 and at most 15 of them, any reachable sum lies within ±135. Index a counting array by sum + offset.
2. Seed the table with one way to reach a total of 0 before any number is placed.
3. For each number x, build a fresh table: every total s with w ways contributes w ways to s + x and w ways to s - x.
4. After all numbers, read off the count at the target.

Why it works

Two different sign assignments that reach the same running total are interchangeable for everything that follows, so collapsing them into a single count loses nothing — that is what turns an exponential 2^n enumeration into a linear sweep over a bounded table. Building a fresh table each round is what keeps each number used exactly once. Note that a 0 in the input legitimately doubles the count, since +0 and -0 are distinct assignments, and the counting handles that automatically.

Complexity

• Time — O(n · sumRange)
• Space — O(sumRange)

Pitfalls

• Totals go negative, so offset the index — a raw sum cannot index an array.
• Build the next table from the previous one rather than updating in place, or a number can be applied twice in one round.
• Zeros double the answer; a set-based "reachable sums" approach silently loses that and undercounts.
• A target outside the reachable range answers 0, not an error.

Reference solution

Python

from typing import List
from collections import defaultdict

def findTargetSumWays(nums: List[int], target: int) -> int:
    counts = {0: 1}
    for x in nums:
        nxt = defaultdict(int)
        for s, c in counts.items():
            nxt[s + x] += c
            nxt[s - x] += c
        counts = nxt
    return counts.get(target, 0)

Java

public static int findTargetSumWays(int[] nums, int target) {
    final int OFFSET = 135, SIZE = 271;
    int[] ways = new int[SIZE];
    ways[OFFSET] = 1;
    for (int x : nums) {
        int[] next = new int[SIZE];
        for (int s = 0; s < SIZE; s++) {
            if (ways[s] == 0) continue;
            if (s + x < SIZE) next[s + x] += ways[s];
            if (s - x >= 0) next[s - x] += ways[s];
        }
        ways = next;
    }
    int idx = target + OFFSET;
    if (idx < 0 || idx >= SIZE) return 0;
    return ways[idx];
}

C++

int findTargetSumWays(vector<int>& nums, int target) {
    const int OFFSET = 135, SIZE = 271;
    vector<int> ways(SIZE, 0);
    ways[OFFSET] = 1;
    for (int x : nums) {
        vector<int> next(SIZE, 0);
        for (int s = 0; s < SIZE; s++) {
            if (ways[s] == 0) continue;
            if (s + x < SIZE) next[s + x] += ways[s];
            if (s - x >= 0) next[s - x] += ways[s];
        }
        ways = next;
    }
    int idx = target + OFFSET;
    if (idx < 0 || idx >= SIZE) return 0;
    return ways[idx];
}

JavaScript

var findTargetSumWays = function(nums, target) {
    let counts = new Map([[0, 1]]);
    for (const x of nums) {
        const next = new Map();
        for (const entry of counts) {
            const sum = entry[0], c = entry[1];
            next.set(sum + x, (next.get(sum + x) || 0) + c);
            next.set(sum - x, (next.get(sum - x) || 0) + c);
        }
        counts = next;
    }
    return counts.get(target) || 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium