Target Sum

mediumTests passed 2026-11-11v1.0.0
TC: O(N * P)|SC: O(P)
2D DPOriginal Statement (leetcode).md

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

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

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]

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.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Coin Change II (O(A * C))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.