Target Sum

Mechanism

Target Sum is a disguised subset-count problem: splitting the array into a '+' group P and a '-' group N means sum(P) - sum(N) = S. Since sum(P) + sum(N) = total (the array's fixed total), adding the two equations gives 2*sum(P) = S + total, so sum(P) = (S + total) / 2. The problem collapses to: count subsets of the array whose sum equals this fixed target subsetSum — exactly the 0/1 knapsack "count subsets with given sum" pattern, solved by a DP table over (index, achievable sum).

Recognize the pattern

• Each element gets exactly one of two mutually exclusive roles (here: + or -) — a binary partition, not a selection of "some" elements.
• A target on a linear combination (sum, difference) of the whole array, not a search over paths or subsequences.
• Array length is small-ish (≤20) but values can be large — hints the state space is (index × achievable-sum), i.e. classic bounded knapsack, not exponential brute force.

Brute force → optimal

Brute force: try both signs for every element recursively — a binary decision tree of depth n, giving O(2^n) time, O(n) space (recursion stack). For n=20 that's ~1,000,000 leaves — survivable but wasteful, and blows up past n=30.

Optimal: reduce to count subsets summing to s = (S + total) / 2, then run the standard 0/1 knapsack counting DP: dp[sum] = number of ways to reach sum using items processed so far. This reuses overlapping subproblems that brute force recomputes from scratch.

Complexity, derived

Let total = sum of all numbers and s = (S+total)/2. The DP table has n rows (items) and s+1 columns (achievable sums 0..s). Each cell dp[i][j] is filled in O(1) from dp[i-1][j] (skip item i) and dp[i-1][j-nums[i]] (take item i) — a direct count-of-ways recurrence, not a search, so total work is exactly n * (s+1) cell fills: O(n * s) time. Space: the 2D table is O(n*s), but since row i only reads row i-1, it collapses to a single 1D array of size s+1 processed right-to-left — O(s) space. Feasibility check: if total < |S| or (S+total) is odd, s is not a non-negative integer and the answer is 0 — this must be checked before allocating the table.

Worked example

nums = {1, 1, 2, 3}, S = 1. total = 7, so s = (1+7)/2 = 4. Count subsets summing to 4. dp array indexed 0..4, dp[0]=1 initially (empty subset sums to 0), rest 0. Each row updates dp[j] += dp[j-num] for j from s down to num.

Check the '+2' row by hand: with items {1,1,2}, only two subsets sum to 2 — {1a,1b} and {2} — so dp[2]=2 (not 3). dp[3]=2 comes from {1,2} using either 1, and dp[4]=1 from {1,1,2}. Carrying this correct row into '+3': dp[3] += dp[0] = 2+1=3, and dp[4] += dp[1] = 1+2=3. Final dp[4] = 3, matching the expected output: {+1-1-2+3}, {-1+1-2+3}, {+1+1+2-3}.

Java (1D DP, count subsets)

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

The inner loop runs right-to-left so each item is only counted once per subset (0/1 knapsack, not unbounded).

Pitfalls

• Forgetting the parity/feasibility check — if (S+total) is odd or total < |S|, s is fractional or unreachable; skipping this causes an array-index or silently wrong answer.
• Iterating the inner sum loop left-to-right instead of right-to-left, which turns 0/1 knapsack into unbounded knapsack (reusing an item multiple times).
• Handling nums[i] = 0: a zero can freely take either sign without changing the sum, so it doubles the running count for every zero in the input. The DP handles this correctly as-is — the update dp[j] += dp[j-0] simplifies to dp[j] += dp[j], i.e. dp[j] doubles for that item, which is exactly the correct behavior; no special-casing is needed.
• Confusing this with "Partition Equal Subset Sum" — that variant asks for existence (boolean), this asks for a count; reusing boolean DP code without switching to counting semantics gives wrong answers.

When to use / when not

Use the subset-sum-count DP when the array is partitioned into exactly two groups by a linear constraint and you need the number of ways — O(n*s) time/O(s) space beats brute force decisively once n exceeds ~25.

Vs. plain recursion with memoization (top-down DP on (index, remainingSum)): same asymptotic complexity, but recursion avoids computing unreachable sums outside the feasible range in sparse cases, at the cost of recursion-stack overhead and slightly worse constant factors. Prefer bottom-up 1D DP when s is reasonably small and dense; prefer memoized recursion when s is huge but the reachable-sum set is sparse.

Vs. brute-force bitmasking/DFS: acceptable only for n ≤ ~20-25 as a fallback or for verifying DP correctness on small tests; never for production-scale n.

Takeaways

• Target Sum is Partition/Subset-Sum in disguise: algebra converts a +/- assignment problem into "count subsets summing to (S+total)/2".
• The DP state is (item index, achievable sum), filled in O(n*s) time; the 1D array optimization requires iterating the sum dimension right-to-left.
• Always validate feasibility (parity, total ≥ |S|) before allocating the DP array.

Recall: Why must the inner sum loop iterate from high to low when compressing the 2D knapsack table to 1D?

Derived from the classic 0/1 knapsack subset-sum-count reduction; complexity analysis and DP formulation are original to this page.