LeetCode 494: Target Sum

Problem Restatement

We are given an integer array nums and an integer target.

For every number in nums, we must choose one sign:

We need to count how many different sign assignments evaluate to target.

For example:

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

There are five valid expressions:

-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

So the answer is 5.

Input and Output

Function shape:

def findTargetSumWays(nums: list[int], target: int) -> int:
    ...

Examples

Example 1:

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

There are five ways to place signs so the result is 3.

Answer:

5

Example 2:

nums = [1]
target = 1

Only one expression works:

+1 = 1

Answer:

1

First Thought: Try Both Signs

For each number, there are two choices:

1. Put + before it.
2. Put - before it.

So we can use recursion.

At index i, keep the current sum. Then branch into:

current + nums[i]
current - nums[i]

When we reach the end, check whether the sum equals target.

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        def dfs(i: int, current: int) -> int:
            if i == len(nums):
                return 1 if current == target else 0

            add = dfs(i + 1, current + nums[i])
            subtract = dfs(i + 1, current - nums[i])

            return add + subtract

        return dfs(0, 0)

This is correct and easy to understand.

Problem With Plain Recursion

There are two choices for every element.

So the recursion explores:

2^n

sign assignments.

Since n <= 20, this may pass in some languages with pruning or memoization, but there is a cleaner dynamic programming transformation.

Key Insight

Split the numbers into two groups:

Then:

P - N = target

Also, every number belongs to exactly one of the two groups:

P + N = sum(nums)

Let:

total = sum(nums)

Subtract the first equation from the second:

(P + N) - (P - N) = total - target
2N = total - target
N = (total - target) / 2

So the problem becomes:

Count how many subsets of nums have sum:

(total - target) // 2

Each such subset is the group that gets the negative sign.

This only works when:

If either condition fails, the answer is 0.

Algorithm

Compute:

total = sum(nums)

If:

abs(target) > total

return 0.

If:

(total - target) % 2 == 1

return 0.

Set:

need = (total - target) // 2

Now count the number of subsets whose sum is need.

Use one-dimensional dynamic programming.

Let:

dp[s]

be the number of ways to choose some processed numbers so their sum is s.

Start with:

dp[0] = 1

There is one way to make sum 0: choose nothing.

For each number num, update sums from high to low:

dp[s] += dp[s - num]

Finally return:

dp[need]

Correctness

Every sign assignment partitions the array into two groups: numbers with plus signs and numbers with minus signs.

If the expression equals target, then the sum of the plus group minus the sum of the minus group equals target.

Together with the total sum equation, this implies that the minus group must have sum:

(total - target) / 2

So every valid expression corresponds to one subset with sum need.

Conversely, every subset with sum need can be assigned the minus sign, while all other numbers receive the plus sign. The resulting expression evaluates to target.

Therefore, counting valid expressions is equivalent to counting subsets with sum need.

The dynamic programming array satisfies this invariant: after processing some prefix of nums, dp[s] is the number of ways to choose a subset from that prefix with sum s.

For each new number num, every subset that makes s - num can become a subset that makes s by adding num. The update adds exactly those choices.

Updating from high to low prevents using the same number more than once in one iteration.

Thus dp[need] is exactly the number of valid sign assignments.

Complexity

Since sum(nums) <= 1000, this is efficient.

Implementation

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        total = sum(nums)

        if abs(target) > total:
            return 0

        if (total - target) % 2 != 0:
            return 0

        need = (total - target) // 2

        dp = [0] * (need + 1)
        dp[0] = 1

        for num in nums:
            for s in range(need, num - 1, -1):
                dp[s] += dp[s - num]

        return dp[need]

Code Explanation

First, compute the maximum possible absolute sum:

total = sum(nums)

If the target is outside that range, no expression can reach it:

if abs(target) > total:
    return 0

The subset target must be an integer:

if (total - target) % 2 != 0:
    return 0

Then compute the sum needed for the negative group:

need = (total - target) // 2

The DP array counts subset sums:

dp = [0] * (need + 1)
dp[0] = 1

For each number, update possible sums:

for num in nums:
    for s in range(need, num - 1, -1):
        dp[s] += dp[s - num]

The descending loop is important because each number can be used at most once.

Finally:

return dp[need]

Memoized DFS Implementation

The direct sign-choice recursion can also be optimized with memoization.

from functools import cache

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        @cache
        def dfs(i: int, current: int) -> int:
            if i == len(nums):
                return 1 if current == target else 0

            return (
                dfs(i + 1, current + nums[i])
                + dfs(i + 1, current - nums[i])
            )

        return dfs(0, 0)

This version follows the problem statement more directly.

Testing

def run_tests():
    s = Solution()

    assert s.findTargetSumWays([1, 1, 1, 1, 1], 3) == 5
    assert s.findTargetSumWays([1], 1) == 1
    assert s.findTargetSumWays([1], -1) == 1
    assert s.findTargetSumWays([1, 2, 3], 0) == 2
    assert s.findTargetSumWays([0, 0, 0, 0, 0], 0) == 32
    assert s.findTargetSumWays([1000], -1000) == 1
    assert s.findTargetSumWays([1, 2, 7], 20) == 0

    print("all tests passed")

run_tests()

Test meaning: