Medium#4948 min readDynamic Programming2D DPKnapsackLeetCode

Target Sum

Subset-sum transform into 1D knapsack

Count knapsack variant. Or transform to subset sum with math.

Published Apr 17, 2026

Problem

Given a non-negative integer array nums and an integer target, you can assign a + or - to each number and concatenate them into an expression. Return the number of ways to build an expression that evaluates to target.

Input

nums = [1, 1, 1, 1, 1], target = 3

Output

Explanation

-1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1.

Input

nums = [1], target = 1

Output

Input

nums = [1], target = 2

Output

Intuition

The naive recursion is 2-way branching per index (+ or -), so exponential in n. Memoization on (i, running_sum) brings it to polynomial but muddles the state space with negative running sums.

There's a cleaner reframe. Let P = sum of the numbers we assign +, N = sum of the numbers we assign -. Then:

P - N = target
P + N = sum

Adding the equations gives 2P = sum + target, so P = (sum + target) / 2. The problem collapses to:

How many subsets of nums sum to P?

That's the counting version of the knapsack reachability DP from #416. Same 1D rolling shape, only dp[j] now stores a count (i32) instead of a boolean.

Pre-conditions the transform needs:

sum + target must be even (otherwise no integer P exists).
|target| > sum is impossible (would require P negative or P > sum).

Fail either check and the answer is 0.

Approach

Memoized Recursion

TimeO(n · sum)

SpaceO(n · sum)

Recurse on (i, running); at each step, either add nums[i] or subtract it. Memoize by (i, running). Works but allocates a HashMap keyed on signed sums — a constant-factor drag vs. the subset-sum transform.

use std::collections::HashMap;

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        let mut memo: HashMap<(usize, i32), i32> = HashMap::new();
        fn go(
            i: usize,
            running: i32,
            nums: &[i32],
            target: i32,
            memo: &mut HashMap<(usize, i32), i32>,
        ) -> i32 {
            if i == nums.len() {
                return if running == target { 1 } else { 0 };
            }
            if let Some(&v) = memo.get(&(i, running)) {
                return v;
            }
            let plus = go(i + 1, running + nums[i], nums, target, memo);
            let minus = go(i + 1, running - nums[i], nums, target, memo);
            let v = plus + minus;
            memo.insert((i, running), v);
            v
        }
        go(0, 0, &nums, target, &mut memo)
    }
}

Rust · runnable

function findTargetSumWays(nums: number[], target: number): number {
  const memo = new Map<string, number>();
  const go = (i: number, running: number): number => {
    if (i === nums.length) return running === target ? 1 : 0;
    const key = `${i},${running}`;
    const cached = memo.get(key);
    if (cached !== undefined) return cached;
    const v = go(i + 1, running + nums[i]) + go(i + 1, running - nums[i]);
    memo.set(key, v);
    return v;
  };
  return go(0, 0);
}

TypeScript · runnable

Subset-Sum 1D Knapsack

TimeO(n · P)

SpaceO(P)

Recommended

Transform: find the count of subsets summing to P = (sum + target) / 2. Then run the counting knapsack — dp[j] starts at 1 for j = 0 (empty subset), zero elsewhere. For each number, iterate j descending and add dp[j - x] into dp[j].

Zeros don't hurt this DP: each zero in nums doubles every count (you can sign a zero + or - without changing the sum). The knapsack handles this implicitly — adding zero to an existing subset yields another equally valid subset; the DP correctly sums both contributions.

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        let sum: i32 = nums.iter().sum();
        if (sum + target) % 2 != 0 || target.abs() > sum {
            return 0;
        }
        let p = ((sum + target) / 2) as usize;
        let mut dp = vec![0i32; p + 1];
        dp[0] = 1;
        for &x in &nums {
            let x = x as usize;
            if x > p {
                continue;
            }
            for j in (x..=p).rev() {
                dp[j] += dp[j - x];
            }
        }
        dp[p]
    }
}

Rust · runnable

function findTargetSumWays(nums: number[], target: number): number {
  const sum = nums.reduce((a, b) => a + b, 0);
  if ((sum + target) % 2 !== 0 || Math.abs(target) > sum) return 0;
  const p = (sum + target) / 2;
  const dp = new Array<number>(p + 1).fill(0);
  dp[0] = 1;
  for (const x of nums) {
    if (x > p) continue;
    for (let j = p; j >= x; j--) {
      dp[j] += dp[j - x];
    }
  }
  return dp[p];
}

TypeScript · runnable

Trace

Subset-sum knapsack on nums = [1, 1, 1, 1, 1], target = 3. Sum = 5, so P = (5 + 3) / 2 = 4.

item	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]
init	1	0	0	0	0
1	1	1	0	0	0
1	1	2	1	0	0
1	1	3	3	1	0
1	1	4	6	4	1
1	1	5	10	10	5

Return dp[4] = 5. ✓

Edge cases

|target| > sum — return 0. No signing can exceed the total magnitude.
(sum + target) odd — return 0. No integer P satisfies both equations.
Zero elements — they double-count in the naive recursion (sign has no effect on sum) but fall out correctly from the knapsack. Both approaches give the same answer.
Empty nums — problem constraints exclude it, but for robustness the subset-sum form returns 1 if target == 0, else 0.

ℹ️

Note

The two-knapsack equation P = (sum + target) / 2 is a standard LC trick. Any "assign ± to each item" problem can be reframed this way: sum of positives minus sum of negatives equals the target, and their total is fixed. Learn this move and you unlock half a dozen problems.

Takeaway

Whenever you see "sign each element ± to hit a target," reach for the P = (sum + target) / 2 reframe before reaching for DFS. It turns an exponential tree into a linear-memory knapsack.

The deeper lesson is that reachability DP (boolean) and counting DP (integer) share the same skeleton — flip dp[j] |= dp[j - x] to dp[j] += dp[j - x] and you're done. This is why #416 and #494 read so similarly despite asking different questions.

Medium#416

Partition Equal Subset Sum

0/1 Knapsack. dp[j] = can we make sum j? Space-optimize to 1D.

More in 2D DP

Medium#62

Unique Paths

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Grid DP starting point.

Medium#1143

Longest Common Subsequence

The classic 2D string DP. Understand match vs. skip transitions.

Medium#416

Partition Equal Subset Sum

0/1 Knapsack. dp[j] = can we make sum j? Space-optimize to 1D.

Medium#72

Edit Distance

dp[i][j] = min edits for s1[0..i] → s2[0..j]. Three transitions: insert, delete, replace.

View #494 on LeetCode