Target Sum | Dynamic Programming on Subsequences

1. Problem Statement & Overview

The Target Sum problem requires us to take an array of integers and assign either a positive (+) or a negative (-) sign to each element such that the algebraic sum of all elements equals a specified target value. We must calculate the total number of ways to assign these signs.

Example Walkthrough

• Given Array: [1, 2, 3, 1]
• Given Target: 3
• Possible Sign Assignments:
  • Way 1: -1 + 2 + 3 - 1 evaluates to 3
  • Way 2: +1 - 2 + 3 + 1 evaluates to 3
• Total Ways: 2

2. Why Do We Need This? (The Status Quo)

When encountering a problem asking to make binary choices (assigning + or -) for every element to reach a target sum, the most instinctive reaction is to write a recursive function.

• Naive Recursive Approach: Try all possible choices (+ or -) for every index, recursively exploring both branches.
• The Catch: While correct, exploring every permutation directly leads to overlapping subproblems and negative indices during target reduction. This makes space optimization and memoization tricky unless we map the problem to an established structural pattern.

3. Core Mental Model & Reduction Strategy

Instead of blindly treating this as an arbitrary sign-assignment problem, we can transform it into a familiar pattern we have solved before: Count Partitions with a Given Difference (DP-18).

Real-Life Analogy: Separating Assets and Liabilities

Imagine grouping your array elements into two separate baskets:

1. Basket S1: Elements that receive a positive (+) sign.
2. Basket S2: Elements that receive a negative (-) sign.

When you sum up everything:

• The sum of elements in S1 is $\text{Sum}(S1)$.
• The sum of elements in S2 is $\text{Sum}(S2)$.
• The total algebraic sum equals our target:

We also know that the sum of both subsets equals the total sum of the array ($\text{TotSum}$):

Adding these two equations together gives us:

Note: This brilliantly reduces the Target Sum problem into finding the number of subsets whose sum equals $\frac{\text{TotSum} + \text{Target}}{2}$. This is identical to the Subset Sum / Count Partitions with Given Difference problem!

4. Edge Cases & Pre-computation Checks

Before diving into the subset sum calculation, we must validate whether a valid partition is mathematically possible. If certain conditions fail, we can immediately return 0 ways:

1. Parity Check: $(\text{TotSum} + \text{target})$ must be even. If $(\text{TotSum} + \text{target}) \% 2 \neq 0$, it is impossible to divide the array into integer subsets, so return 0.
2. Range Check: The target must not exceed the total sum of the array. If target > TotSum or target < -TotSum, return 0.

5. Step-by-Step Code Evolution

Naive Recursive Signature (Concept)

function solve(index: number, currentTarget: number): number {
    // Base cases and recursive choices (+/-)
}

Reduced Tabulated Implementation

Since we can reuse our proven Count Partitions with Given Difference code (from DP-18), we simply compute the required subset sum s1 and invoke the subset counting engine.

#include <vector>
#numeric>
#include <numeric>

class Solution {
private:
    int countSubsets(vector<int>& arr, int target) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        
        // Base case for element 0
        if (arr[0] == 0) dp[0][0] = 2; // Choosing or not choosing 0
        else dp[0][0] = 1; // Not choosing 0
        
        if (arr[0] != 0 && arr[0] <= target) {
            dp[0][arr[0]] = 1;
        }
        
        for (int ind = 1; ind < n; ind++) {
            for (int sum = 0; sum <= target; sum++) {
                int notTaken = dp[ind - 1][sum];
                int taken = 0;
                if (arr[ind] <= sum) {
                    taken = dp[ind - 1][sum - arr[ind]];
                }
                dp[ind][sum] = (notTaken + taken);
            }
        }
        return dp[n - 1][target];
    }

public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int totSum = 0;
        for (int num : nums) totSum += num;
        
        // Edge condition checks
        if (totSum - target < 0 || (totSum - target) % 2 != 0) return 0;
        
        int s2 = (totSum - target) / 2;
        return countSubsets(nums, s2);
    }
};

6. Complete Flow Walkthrough

7. Comparison: Direct Recursion vs. Subset Transformation

8. Summary and Key Takeaways

• Pattern Recognition: The Target Sum problem is disguised as a sign-assignment task, but is structurally identical to Partition Subset Sum with a Given Difference.
• Mathematical Reduction: Splitting elements into positive ($S1$) and negative ($S2$) subsets reduces the problem to finding subsets that sum to $\frac{\text{TotSum} - \text{Target}}{2}$.
• Avoid Direct Target Subtraction: Direct recursion with negative targets complicates space limits and memoization state boundaries.
• Always Validate Parity: Check whether $(\text{TotSum} - \text{target})$ is non-negative and even before running DP algorithms.
• Reusability: Leveraging pre-built templates like Subset Sum saves implementation time and prevents edge-case bugs.