MediumArrayDynamic ProgrammingBacktracking

Target Sum

1 approach, code in every language

You are given an array of non-negative integers and an integer target. You must place either a plus sign or a minus sign in front of every number and then concatenate them into an arithmetic expression.

For example, with the numbers [2, 1] you could form +2+1, +2-1, -2+1, or -2-1. Each choice of signs yields one expression and one resulting value.

Return the number of distinct sign assignments that make the expression evaluate exactly to target.

Example 1

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

Output: 5

There are five ways to choose signs that sum to 3, each turning exactly one of the ones negative: -1+1+1+1+1, +1-1+1+1+1, and so on.

Example 2

Input: nums = [1], target = 1

Output: 1

Only assigning a plus sign to the single 1 reaches the target, so there is exactly one valid assignment.

Constraints

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

Reduce to Counting Subset Sums

Let P be the sum of the positively signed numbers; then P = (total + target)/2, and the answer is the number of subsets summing to P computed with a counting DP.

Loading animation…

Intuition

Split the numbers into a positive group with sum P and a negative group with sum N. Then P - N equals the target and P + N equals the total, so adding those equations gives P = (total + target) / 2. If total + target is negative or odd, no valid assignment exists, so we return 0. Otherwise the problem becomes counting how many subsets of the numbers add up to exactly P, which is a 0/1 knapsack counting problem. We accumulate counts with dp[s] += dp[s - num], iterating sums downward so each number is used at most once.

Algorithm walkthrough

1Compute total. If (total + target) is negative or odd, return 0 because P would not be a non-negative integer.
2Set P = (total + target) / 2, the required sum of the positively signed subset.
3Create a counting array dp of size P + 1 with dp[0] = 1, representing one way to reach a sum of zero (choose nothing).
4For each number, iterate s from P down to the number and add dp[s - num] into dp[s], counting subsets that include the current number.
5Return dp[P], the total number of subsets that sum to P and therefore the number of valid sign assignments.

Implementation

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if (total + target) < 0 or (total + target) % 2 != 0:
            return 0
        p = (total + target) // 2
        dp = [0] * (p + 1)
        dp[0] = 1
        for num in nums:
            for s in range(p, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[p]

Time

O(n * P) where P = (total + target)/2; each number sweeps the count array once.

Space

O(P) for the one-dimensional counting DP array.

Because sum(nums) is at most 10^4, P stays small and the counting DP is far faster than the 2^n brute-force sign enumeration.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Thruster Burn Plans is our own problem on the technique behind Target Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free