LeetCode 494 Target Sum - Implementation

function findTargetSumWays(nums, target)
    total := sum of all nums
    if (target + total) is odd then
        return 0
    if abs(target) > total then
        return 0
    subset := (target + total) / 2
    dp := array of size (subset + 1), all 0
    dp[0] := 1
    for each num in nums
        for s from subset down to num
            dp[s] := dp[s] + dp[s - num]
    return dp[subset]

Time: $O(n \times subset)$. Space: $O(subset)$.

This counts combinations, so you add dp[s - num] instead of OR-ing. The backwards loop ensures each element is used exactly once per combination.

The math transformation from $P - N = target$ to $P = (target + total)/2$ is the key insight. Once you see it, the problem becomes standard subset sum.