Target Sum

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonFacebookGoogle

Given an array of non-negative integers and a target value, count how many different ways a plus or minus sign can be placed in front of every number so that the resulting expression evaluates to exactly the target. Every number must receive exactly one sign, and every distinct choice of signs counts as a separate way, even if two choices happen to use the same signs on equal-valued numbers at different positions. Splitting the numbers by the sign they end up with turns this into a partition question: the numbers assigned a plus sign form one group, the numbers assigned a minus sign form the other, and the group sums are related to the target and the array's total in a fixed way — knowing any two of "positive group sum," "negative group sum," and "target" pins down the third. That reduces the problem to counting how many subsets of the array sum to one specific, precomputed amount — the same counting search used for Count Subsets with Sum K, just with that amount derived from the total and the target first.

Test Case 1:

Input:nums = [2, 3, 4, 1], target = 2

Output:2

Explanation:Two sign assignments reach 2: +2 +3 -4 +1 = 2, and +2 -3 +4 -1 = 2.

Test Case 2:

Input:nums = [5, 3, 2], target = 0

Output:2

Explanation:Two sign assignments reach 0: +5 -3 -2 = 0, and -5 +3 +2 = 0.

Test Case 3:

Input:nums = [1, 2, 1], target = 4

Output:1

Explanation:Only one sign assignment reaches 4: +1 +2 +1 = 4 (the maximum possible, so it's the only way).

Constraints

◆1 ≤ nums.length ≤ 20
◆0 ≤ nums[i] ≤ 100
◆0 ≤ target ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Every number gets exactly one of two signs, so track the running total as each number is added in or subtracted out in turn. Once every number has been assigned a sign, this particular assignment counts as valid only if the running total lands exactly on the target — so, like counting subsets with a given sum, the check has to wait until every number has been decided, since a number with value 0 could be assigned either sign without changing the total at all, and each of those is still a distinct assignment. Both signs are tried for every number, and the total count is the number of complete assignments that hit the target exactly.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;
    private int target;

    public int targetSum(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        return solve(0, 0);
    }

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

Optimal — Bottom-Up 1D DP

Optimal

Split the numbers into the ones assigned a plus sign (call their total P) and the ones assigned a minus sign (call their total N). Then P - N = target and P + N = the array's total, which pins N down to a single fixed value the moment the total and target are known: N = (total - target) / 2. That value has to be a non-negative whole number for any valid assignment to exist; when it isn't, the answer is immediately 0. Otherwise, the question becomes exactly Count Subsets with Sum K for that fixed N: sweep each number's contribution into a running count of how many subsets reach each amount up to N, and the count at N once every number has been swept through is the answer.

TimeO(n × sum)

SpaceO(sum)