259. Target Sum

Split nums into a positive group P and a negative group N. Since P - N = target and P + N = total, P = (total + target) / 2. So the answer is the number of subsets summing to that fixed value.

The transformation

Let P be the numbers we prefix with + and N those with -.

• P - N = target
• P + N = total (the sum of all numbers)

Adding: 2P = total + target, so P = (total + target) / 2. If that isn't a non-negative integer (or |target| > total), the answer is 0.

Now the problem is: how many subsets of nums sum to P? — a classic 0/1 subset-count DP.

DP

dp[s] = number of subsets summing to s, with dp[0] = 1. For each num, sweep s downward from P to num (0/1 knapsack): dp[s] += dp[s - num].

Worked example

nums = [1,1,1,1,1], target = 3: total = 5, P = (5+3)/2 = 4. Subsets summing to 4 = choose 4 of the five 1's = 5.

Complexity

• Time: O(n · P).
• Space: O(P).

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int n : nums) total += n;
        if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
        int subset = (total + target) / 2;
        int[] dp = new int[subset + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int s = subset; s >= num; s--) {
                dp[s] += dp[s - num];
            }
        }
        return dp[subset];
    }
}