# 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:

| Sign | Meaning |
|---|---|
| `+` | Add this number |
| `-` | Subtract this number |

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

For example:

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

There are five valid expressions:

```text
-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

| Item | Meaning |
|---|---|
| Input | Integer array `nums`, integer `target` |
| Output | Number of sign assignments that evaluate to `target` |
| Constraint | `1 <= nums.length <= 20` |
| Value range | `0 <= nums[i] <= 1000` |
| Sum range | `0 <= sum(nums[i]) <= 1000` |
| Target range | `-1000 <= target <= 1000` |

Function shape:

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

## Examples

Example 1:

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

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

Answer:

```python
5
```

Example 2:

```python
nums = [1]
target = 1
```

Only one expression works:

```text
+1 = 1
```

Answer:

```python
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:

```python
current + nums[i]
current - nums[i]
```

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

```python
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:

```text
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:

| Group | Meaning |
|---|---|
| `P` | Numbers with a plus sign |
| `N` | Numbers with a minus sign |

Then:

```text
P - N = target
```

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

```text
P + N = sum(nums)
```

Let:

```python
total = sum(nums)
```

Subtract the first equation from the second:

```text
(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:

```python
(total - target) // 2
```

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

This only works when:

| Condition | Reason |
|---|---|
| `abs(target) <= total` | Otherwise the target is too large to reach |
| `total - target` is even | Otherwise `N` is not an integer |

If either condition fails, the answer is `0`.

## Algorithm

Compute:

```python
total = sum(nums)
```

If:

```python
abs(target) > total
```

return `0`.

If:

```python
(total - target) % 2 == 1
```

return `0`.

Set:

```python
need = (total - target) // 2
```

Now count the number of subsets whose sum is `need`.

Use one-dimensional dynamic programming.

Let:

```python
dp[s]
```

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

Start with:

```python
dp[0] = 1
```

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

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

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

Finally return:

```python
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:

```text
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * total)` | We process each number across possible sums |
| Space | `O(total)` | The DP array stores counts for subset sums |

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

## Implementation

```python
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:

```python
total = sum(nums)
```

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

```python
if abs(target) > total:
    return 0
```

The subset target must be an integer:

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

Then compute the sum needed for the negative group:

```python
need = (total - target) // 2
```

The DP array counts subset sums:

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

For each number, update possible sums:

```python
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:

```python
return dp[need]
```

## Memoized DFS Implementation

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

```python
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

```python
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:

| Test | Why |
|---|---|
| `[1, 1, 1, 1, 1], 3` | Main example |
| `[1], 1` | Single positive sign |
| `[1], -1` | Single negative sign |
| `[1, 2, 3], 0` | Multiple valid sign assignments |
| `[0, 0, 0, 0, 0], 0` | Zero doubles the number of choices each time |
| `[1000], -1000` | Boundary value |
| `[1, 2, 7], 20` | Target impossible |