Topics › Dynamic Programming › DP on Subsequences

Target sum

Hard TUF ID 324 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array nums of non-negative integers and an integer target. Build an expression by writing either + or - in front of every element, in order, and evaluating the result. Count the number of different sign assignments whose value equals target.

This is LeetCode 494. Constraints: 1 ≤ n ≤ 20, 0 ≤ nums[i] ≤ 1000, the sum of all elements is at most 1000, and -1000 ≤ target ≤ 1000. The answer is at most 2^20, so an int is enough and no modulo is needed.

Example 1

nums = [1, 1, 1, 1, 1], target = 3
answer = 5          // exactly one of the five 1s gets a minus sign, and there are 5 ways to choose it

Example 2

nums = [1, 2, 7, 1], target = 9
answer = 2          // +1 +2 +7 -1 = 9 and -1 +2 +7 +1 = 9

Approach 1: Recursion over the signs

Intuition. Every element gets one of two signs, so there are 2^n expressions. Walk left to right carrying the running value cur of the signs chosen so far. At the end, the expression counts if cur == target. The number of valid expressions from a point is the number with +nums[i] next plus the number with -nums[i] next; these sets never overlap, so the counts add.

Algorithm.

1. signs(i, cur): if i == n, return 1 if cur == target, else 0.
2. Otherwise return signs(i + 1, cur + nums[i]) + signs(i + 1, cur - nums[i]).

static int recursive(int[] nums, int target) {
    return signs(0, 0, nums, target);
}

static int signs(int i, int cur, int[] nums, int target) {
    if (i == nums.length) return cur == target ? 1 : 0;
    return signs(i + 1, cur + nums[i], nums, target)            // +nums[i]
         + signs(i + 1, cur - nums[i], nums, target);           // -nums[i]
}

Complexity. Time O(2^n), which for n = 20 is about a million calls and actually passes. Space O(n) recursion depth. Still, it is worth seeing how DP removes the repetition.

Approach 2: Memoization with an offset

Intuition. The future depends only on (i, cur). With nums = [1, 1, 1, 1, 1], the prefixes +1 -1 and -1 +1 both reach (2, 0), and from there the count is the same. The running value always lies between -total and total, so a table with 2 · total + 1 columns covers every possible cur. Java arrays cannot have negative indices, so column cur + total stores the entry for cur. This offset trick is the standard way to memoize on a value that can be negative.

Algorithm.

1. Compute total. Allocate dp[n][2 · total + 1] filled with -1.
2. Same recursion, reading and writing dp[i][cur + total].

static int memoization(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;
    int[][] dp = new int[nums.length][2 * total + 1];           // running total ranges over [-total, total]
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, 0, nums, target, total, dp);
}

static int memo(int i, int cur, int[] nums, int target, int total, int[][] dp) {
    if (i == nums.length) return cur == target ? 1 : 0;
    if (dp[i][cur + total] != -1) return dp[i][cur + total];
    int ways = memo(i + 1, cur + nums[i], nums, target, total, dp)
             + memo(i + 1, cur - nums[i], nums, target, total, dp);
    return dp[i][cur + total] = ways;
}

Complexity. Time O(n · total): at most n · (2 · total + 1) states, each solved once. Space the same, plus O(n) stack.

The reduction to counting subsets

Split the elements by sign: let P be the sum of the elements written with + and N the sum of those written with -. Then

P + N = total
P - N = target

Subtracting gives 2N = total - target, so N = (total - target) / 2. A sign assignment is completely described by which elements get the minus sign, so:

The number of expressions equals the number of subsets of nums with sum (total - target) / 2.

This is Count partitions with given difference with d = target, and therefore Count subsets with sum K. It also tells us when the answer is 0 without any DP:

• If |target| > total, even making every sign agree cannot reach it.
• If total - target is odd, N would not be an integer.

Negative targets are handled by symmetry: flipping every sign turns an expression worth target into one worth -target, a one-to-one correspondence. So we can work with t = |target|, which also guarantees N = (total - t) / 2 lies in [0, total / 2].

The new table has N + 1 ≤ total / 2 + 1 columns, about a quarter of the 2 · total + 1 used by the offset memo.

Approach 3: Tabulation

Intuition. Count subsets of the first i elements with sum s, row by row. Use the prefix-length base case dp[0][0] = 1 (only the empty subset, sum 0) and start the inner loop at s = 0. That keeps zeros correct: a zero can carry either sign, and +0 and -0 are different expressions, so each zero must double the count. With dp[i][s] = dp[i - 1][s] + dp[i - 1][s - 0] it does.

Algorithm.

1. Compute total, t = |target|. If t > total or total - t is odd, return 0.
2. neg = (total - t) / 2; dp[0][0] = 1.
3. For i = 1..n, s = 0..neg: dp[i][s] = dp[i - 1][s] + (nums[i - 1] ≤ s ? dp[i - 1][s - nums[i - 1]] : 0).
4. Return dp[n][neg].

static int tabulation(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;
    int t = Math.abs(target);                                    // flipping every sign maps target to -target
    if (t > total || (total - t) % 2 != 0) return 0;
    int neg = (total - t) / 2;                                   // the elements given a minus sign must sum to this
    int n = nums.length;
    int[][] dp = new int[n + 1][neg + 1];                        // dp[i][s]: subsets of the first i elements with sum s
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= neg; s++) {
            dp[i][s] = dp[i - 1][s] + (nums[i - 1] <= s ? dp[i - 1][s - nums[i - 1]] : 0);
        }
    }
    return dp[n][neg];
}

Complexity. Time O(n · total), space O(n · total), with a smaller constant than the memo.

Approach 4: Space optimized

Intuition. Keep a single array ways and, for each element x, update ways[s] += ways[s - x] for s from neg down to x. Reading a smaller index that has not been updated yet for x means x is used at most once, as each element appears once in the expression.

Algorithm.

1. Same rejection tests and neg as before; ways[0] = 1.
2. For each x, for s from neg down to x: ways[s] += ways[s - x].
3. Return ways[neg].

static int spaceOptimized(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;
    int t = Math.abs(target);
    if (t > total || (total - t) % 2 != 0) return 0;
    int neg = (total - t) / 2;
    int[] ways = new int[neg + 1];
    ways[0] = 1;
    for (int x : nums) {
        for (int s = neg; s >= x; s--) ways[s] += ways[s - x];   // right to left: each element used at most once
    }
    return ways[neg];
}

Dry run on Example 1: total = 5, t = 3, so neg = 1. The array has two cells, ways[0] and ways[1].

ways[1] = 5: five ways to choose the single element that gets the minus sign.

Complexity. Time O(n · total), space O(total).

Edge cases and pitfalls

• Zeros. [0, 0, 0, 0, 0, 0, 0, 0, 1] with target 1 gives 256: the 1 must be positive and each of the eight zeros takes either sign. A base case that returns early when the remaining sum hits 0 would undercount.
• [0] with target 0. The answer is 2 (+0 and -0), not 1.
• Negative target. Using |target| keeps neg within [0, total / 2]. The signed formula (total - target) / 2 also gives the right count, but then the rejection test must be |target| > total rather than target > total; otherwise a target such as -5000 slips through and allocates a needlessly wide table.
• Unreachable target. |target| > total returns 0 immediately; [1] with target 2 is an example.
• Parity. [1, 2] with target 2: total - target = 1 is odd, so the answer is 0.
• Memo sentinel. Counts can be 0, so the offset table uses -1 for “not computed”.
• Testing. The Java file cross-checks all methods on 300 seeded random inputs with zeros and negative targets.

Related problems

• Count partitions with given difference is the same problem after the sign-to-group reduction.
• Count subsets with sum K is the counting DP used by Approaches 3 and 4.
• Partition equal subset sum asks whether some assignment reaches target 0.
• Coin Change 2 (DP - 22) counts combinations when each value may be used any number of times.