Target Sum

Medium Problem 132 of 151 Java and Python

Problem

You are given an integer array nums and an integer target. Put a + or - before each number and concatenate them into an expression.

Return the number of different expressions that evaluate to target.

Example 1

Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Why: Any one of the five 1s gets the minus sign.

Example 2

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

Constraints

1 ≤ nums.length ≤ 20
0 ≤ nums[i] ≤ 1000, sum(nums) ≤ 1000

Explanation

Split the numbers into a plus group P and a minus group N. Then P - N = target and P + N = total, so P = (total + target) / 2.

So the question becomes: how many subsets sum to (total + target) / 2? That is a counting 0/1 knapsack. If total + target is odd or negative, the answer is 0.

Approach 1 · Naive

Try every sign

Time O(2ⁿ)
Space O(n)

Recursively choose + or - for each number and count the expressions that hit the target.

count(i, sum): at the end, return 1 if sum == target, else 0.
Return count(i + 1, sum + nums[i]) + count(i + 1, sum - nums[i]).

Java

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);
    }
}

Python

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def count(i, total):
            if i == len(nums):
                return 1 if total == target else 0
            return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])

        return count(0, 0)

Approach 2 · Optimal

Count subsets with sum P

Time O(n · total)
Space O(total)

Reduce to counting subsets that sum to (total + target) / 2, using a 1-D knapsack table with sums looped downwards.

If |target| > total or (total + target) is odd, return 0.
goal = (total + target) / 2; ways[0] = 1.
For each number x, for s from goal down to x: ways[s] += ways[s - x].
Return ways[goal].

Java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        if (Math.abs(target) > total || (total + target) % 2 != 0) {
            return 0;
        }
        int goal = (total + target) / 2;
        int[] ways = new int[goal + 1];
        ways[0] = 1;
        for (int x : nums) {
            for (int s = goal; s >= x; s--) {
                ways[s] += ways[s - x];
            }
        }
        return ways[goal];
    }
}

Python

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

Complexity compared

Approach	Time	Space
Naive Try every sign	O(2ⁿ)	O(n)
Optimal Count subsets with sum P	O(n · total)	O(total)

Key takeaways

A little algebra can turn a ± problem into a subset problem; look for it when signs are chosen freely.
Zeros in nums double the count (±0), and the s >= x loop with x = 0 handles that correctly.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem