LeetCode 494. Target Sum — 0/1 Knapsack Reframed

This post solves LeetCode 494. Target Sum by converting it into a subset sum / 0-1 knapsack counting problem.

---

Problem Summary

You are given an array nums and a target.
By placing '+' or '-' in front of each number, you create an expression such as:

+2 -1
-3 +4 -2

Your task is to compute how many different expressions evaluate to the target.

Examples

nums = [1,1,1,1,1], target = 3 → 5 ways
nums = [1], target = 1 → 1 way

Constraints:

• 1 <= nums.length <= 20

• 0 <= nums[i] <= 1000

• Total sum(nums) ≤ 1000

• Target ∈ [−1000, 1000]

---

Step 1: Convert +/− to Two Sets (Key Insight)

Let:

• P = sum of numbers assigned +

• N = sum of numbers assigned - (absolute values)

The expression evaluates to:

P - N = target
P + N = sum(nums) = S

Solving these equations:

2P = target + S
P = (target + S) / 2

This means:

We just need to count how many subsets of nums sum up to P.

This is exactly the 0/1 knapsack (subset sum) problem.

---

Step 2: Validate Edge Cases

We must ensure:

1. (target + S) is even

2. |target| <= S

Otherwise, no subsets can reach the target.

---

Step 3: DP Definition (Counting Ways)

Define:

dp[j] = number of ways to choose some nums whose sum = j

Initialization:

dp[0] = 1

There is exactly one way to form sum 0: choose nothing.

Transition (0/1 knapsack, reversed iteration):

for each num in nums:
    for j from P down to num:
        dp[j] += dp[j - num]

We must iterate right → left to prevent reusing the same number multiple times.

---

Final Java Code

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum += num;

        // Impossible cases
        if (Math.abs(target) > sum || (target + sum) % 2 != 0) {
            return 0;
        }

        int P = (target + sum) / 2;
        int[] dp = new int[P + 1];
        dp[0] = 1; // one way to make sum 0

        for (int num : nums) {
            for (int j = P; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[P];
    }
}

---

Time & Space Complexity

• Time: O(n * P) where P ≤ 1000

• Space: O(P) since we use 1D DP

---

Key Takeaways

• The plus/minus assignment translates naturally into a two-set partition.

• Rearranging equations reveals a subset sum problem.

• Use dp[j] += dp[j - num] to count ways, not maximize values.

• Initialize dp[0]=1, and iterate from right to left.

This problem is a great example of how an expression-building puzzle maps cleanly onto 0/1 knapsack.