The O(n) Club: Target Sum — Why Subset Sums Deserve an Oscar for Best Disguise

The O(n) Club: Target Sum — Why Subset Sums Deserve an Oscar for Best Disguise

⚡ TL;DR

Want your array to hit the target by just flipping plus and minus signs? It’s not magic; it’s subset sum in a trench coat. Brute force? Go ahead—if you’d like your code to time out faster than your morning coffee cools:

// Recursion that will haunt your CPU
int countWays(int[] nums, int target) {
  return helper(nums, 0, target);
}
int helper(int[] nums, int idx, int sum) {
  if (idx == nums.length) return sum == 0 ? 1 : 0;
  return helper(nums, idx + 1, sum - nums[idx])
       + helper(nums, idx + 1, sum + nums[idx]);
}
  

🧠 How Devs Usually Mess This Up

Oh, the classics. Folks toss recursion at it, get lost in exponential woods, or treat it like Two Sum’s dramatic cousin. Or, for extra fun, they whip up a DP solution that cries the first time it sees a negative index. You can’t just summon up dp[-1] and hope the compiler’s feeling generous.

• Negative Numbers: Regular DP doesn’t speak negative. If you try, you’ll get array-out-of-bounds and existential dread in equal measure.
• Updating the DP Array Wrong: Iterate DP left-to-right? Oops, you’ve just overcounted like a toddler at a candy shop.
• Parity Police: If (sum + target) is odd, you’re basically asking for an unmakeable combo meal. Check before you invest your coding energy.
• Confusing with Two Sum: Despite the name, you can’t just pair numbers and call it a day. Sorry, interviewers are unfazed by your optimism.

🔍 What’s Actually Going On

This is subset sum in cosplay. Visualize your array as two rooms: one where you hand out ‘+’ stickers, one for ‘-‘. Want their difference to be ‘target’? It all distills down to high school algebra:

• Group the positive and negative piles: P - N = target and P + N = total_sum
• Add them up: 2P = target + total_sum ⇒ P = (target + total_sum) / 2
• So you just need to count how many subsets sum to P. No signs, no drama—just classic DP, but only if (target + total_sum) divides by 2 evenly.

Sneaky, eh? Turns out, flipping signs is just a fancy way to make subset sum look cooler.

🛠️ PseudoCode

• Calculate total sum:

  int S = Arrays.stream(nums).sum();

  Return 0 early if S < abs(target), or (S + target) is odd.
• Set subset sum target: P = (S + target) / 2.
• Initialize DP array:

  int[] dp = new int[P + 1];
  dp[0] = 1;

  One way to build sum zero: use nothing.
• For each num in nums:

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

  Iterate backwards or you’ll double-book those numbers like a disastrous calendar app.
• Return dp[P] as your answer. Done!

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Impossible Targets: If (total_sum + target) is odd, or abs(target) > total_sum, congrats—you’re done, with zero ways.
• Zeroes Magnetize the Answer: Each zero doubles your count, because it can be ignored or included for free (plus or minus: it does nothing but show up twice in your count).
• DP Direction: Always iterate from big to small, or you’ll overcount. If you go the other way, DP will gaslight you with wrong results.
• Complexities: O(N * P) time and O(P) space. No, it’s not constant; yes, that’s as good as Java gets here.

🧠 Interviewer Brain-Tattoo

Target Sum isn’t just Two Sum in an existential rut—it’s Subset Sum with an identity crisis and some high school algebra thrown in. Reduce, reframe, and for the love of Stack Overflow, loop your DP in the right direction.