Target Sum

Medium Dynamic Programming Knapsack Original on LeetCode

Target Sum is a medium dynamic programming problem solved with the knapsack pattern. The best approach, optimal (count subsets with sum p), runs in O(n · S) time and O(S) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every sign) up.

Problem

You are given an integer array nums and an integer target. Put either a + or a - sign in front of every element of nums, then add everything up to form an expression.

Return how many different sign assignments make the expression evaluate to exactly target. Two assignments are different if at least one position gets a different sign, even when the numbers are equal.

Examples

Example 1

Input
nums = [2, 2, 2], target = 2
Output
3
Why
Exactly one of the three 2s must get a minus sign: -2+2+2, +2-2+2 and +2+2-2 all give 2.

Example 2

Input
nums = [1, 3, 4], target = 0
Output
2
Why
+1+3-4 = 0 and -1-3+4 = 0; no other sign pattern reaches 0.

Example 3

Input
nums = [5], target = 3
Output
0
Why
A single 5 can only become +5 or -5.

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums) <= 1000
  • -1000 <= target <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every sign)O(2^n)O(n)
Better (memoized recursion)O(n · S)O(n · S)
Optimal (count subsets with sum P)O(n · S)O(S)

1Brute force (try every sign)

TimeO(2^n)Each of the n numbers splits the search into two branches.
SpaceO(n)The recursion depth is n.

Recursively walk the array. At each index, try adding the number and try subtracting it. When all numbers are used, count 1 if the running sum equals the target.

  1. count(i, sum): if i == n, return 1 if sum == target else 0.
  2. Return count(i + 1, sum + nums[i]) + count(i + 1, sum - nums[i]).
  3. The answer is count(0, 0).
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return count(nums, 0, 0, target);
    }

    private int count(int[] nums, int i, int sum, int target) {
        if (i == nums.length) return sum == target ? 1 : 0;
        return count(nums, i + 1, sum + nums[i], target)
             + count(nums, i + 1, sum - nums[i], target);
    }
}

2Better (memoized recursion)

TimeO(n · S)S = sum(nums); each of the n · (2S + 1) states is computed once in O(1).
SpaceO(n · S)The memo table has n · (2S + 1) entries.

The running sum always stays between -total and +total, so the state (i, sum) has only n * (2 * total + 1) values. Cache the count for each state, shifting the sum by total to use it as an array index.

  1. Compute total; if |target| > total return 0.
  2. memo[i][sum + total] stores count(i, sum), initially unknown.
  3. Same recursion as brute force, but return the cached value when present.
class Solution {
    private Integer[][] memo;
    private int total;

    public int findTargetSumWays(int[] nums, int target) {
        total = 0;
        for (int x : nums) total += x;
        if (Math.abs(target) > total) return 0;
        memo = new Integer[nums.length][2 * total + 1];
        return count(nums, 0, 0, target);
    }

    private int count(int[] nums, int i, int sum, int target) {
        if (i == nums.length) return sum == target ? 1 : 0;
        if (memo[i][sum + total] != null) return memo[i][sum + total];
        int ways = count(nums, i + 1, sum + nums[i], target)
                 + count(nums, i + 1, sum - nums[i], target);
        memo[i][sum + total] = ways;
        return ways;
    }
}

3Optimal (count subsets with sum P)

TimeO(n · S)For each of the n numbers, at most S + 1 sums are updated.
SpaceO(S)One array of size P + 1 ≤ S + 1.

Split the numbers into a plus group with sum P and a minus group with sum total - P. Then P - (total - P) = target, so P = (total + target) / 2. The answer is the number of subsets summing to P, a classic 0/1 knapsack count with a single 1D array filled from high sums to low.

  1. If |target| > total or (total + target) is odd, return 0.
  2. P = (total + target) / 2; ways[0] = 1.
  3. For each x in nums, for s from P down to x: ways[s] += ways[s - x].
  4. Return ways[P].
class Solution {
    public 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 p = (total + target) / 2;
        int[] ways = new int[p + 1];
        ways[0] = 1;
        for (int x : nums) {
            for (int s = p; s >= x; s--) {
                ways[s] += ways[s - x];
            }
        }
        return ways[p];
    }
}

Edge cases to test

  • Zeros in the array: each 0 doubles the count, because +0 and -0 are different sign choices
  • A target whose absolute value is larger than the total sum gives 0
  • When total + target is odd, no assignment can work
  • A negative target is symmetric to the positive one

Hints

Hint 1

Every number gets exactly one of two signs, so there are 2^n expressions. Can you count them recursively?

Hint 2

The state is just (index, running sum). Many different sign prefixes land on the same state, so cache it.

Hint 3

Let P be the sum of the plus group. Then P - (total - P) = target, so P = (total + target) / 2. Count the subsets that sum to P.

FAQ

What is the best time complexity for Target Sum?

Optimal (count subsets with sum P) runs in O(n · S) time and O(S) extra space. For each of the n numbers, at most S + 1 sums are updated.

Which pattern does Target Sum use?

It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.

Is there a brute force solution for Target Sum?

Yes. Brute force (try every sign) takes O(2^n) time and O(n) space. Recursively walk the array.

Which edge cases should I test for Target Sum?

Zeros in the array: each 0 doubles the count, because +0 and -0 are different sign choices; A target whose absolute value is larger than the total sum gives 0; When total + target is odd, no assignment can work; A negative target is symmetric to the positive one.