# Target Sum

- **Canonical ID**: `target-sum`
- **Canonical URL**: https://dsacheatsheet.com/problems/target-sum
- **Difficulty**: medium
- **Patterns**: 2D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/target-sum/

## 1. Core Invariant / The Trick

Algebraic reduction to 0/1 Subset Sum: partition `nums` into positive `P` and negative `N` subsets: `P - N = target` and `P + N = total`, so `P = (total + target) / 2`. Count subsets summing to `P` with backward 0/1 knapsack `dp[s] += dp[s - x]`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N * P)`
- **Space Complexity**: `O(P)`
- **Proof**: Replaces signed offsets `[-total..+total]` with a half-sized non-negative subset-sum DP table updated backward to enforce single use per element.

## 3. Minimal Idiomatic Code

### Python
```python
def findTargetSumWays(nums: list[int], target: int) -> int:
    total = sum(nums)
    if abs(target) > total or (total + target) % 2 != 0:
        return 0
    P = (total + target) // 2
    dp = [0] * (P + 1)
    dp[0] = 1
    for x in nums:
        for s in range(P, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[P]
```

### TypeScript
```typescript
export function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;
  const P = (total + target) >> 1;
  const dp = new Int32Array(P + 1);
  dp[0] = 1;
  for (const x of nums) {
    for (let s = P; s >= x; s--) dp[s] += dp[s - x];
  }
  return dp[P];
}
```

### C++
```cpp
int findTargetSumWays(vector<int>& nums, int target) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (abs(target) > total || (total + target) % 2 != 0) return 0;
    int P = (total + target) / 2;
    vector<int> dp(P + 1, 0);
    dp[0] = 1;
    for (int x : nums)
        for (int s = P; s >= x; --s) dp[s] += dp[s - x];
    return dp[P];
}
```

### Java
```java
int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;
    if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
    int P = (total + target) / 2;
    int[] dp = new int[P + 1];
    dp[0] = 1;
    for (int x : nums)
        for (int s = P; s >= x; s--) dp[s] += dp[s - x];
    return dp[P];
}
```

### Go
```go
func findTargetSumWays(nums []int, target int) int {
    total := 0
    for _, x := range nums { total += x }
    if target > total || -target > total || (total+target)%2 != 0 { return 0 }
    P := (total + target) / 2
    dp := make([]int, P+1)
    dp[0] = 1
    for _, x := range nums {
        for s := P; s >= x; s-- { dp[s] += dp[s-x] }
    }
    return dp[P]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Failing early checks `abs(target) > total` or `(total + target) & 1 != 0` accesses invalid indices.
- Updating `s` *forward* instead of *backward* reuses elements (unbounded knapsack bug!).

### Follow-ups
- Partition Equal Subset Sum sets `target = 0` (`P = total // 2`) with boolean OR instead of count.