Target Sum

Problem Statement

You are given an integer array nums and an integer target. You want to build an expression using + and - operators on elements in nums such that the final result is equal to the target.

Return the number of ways to assign symbols to make the sum equal to target.

Intuition

We are to assign either a + or - sign to each number. This creates two subsets:

One subset with positive signs: S1
One subset with negative signs: S2

The total sum of array = S = S1 + S2
Required: S1 - S2 = target
→ So,

S1 - S2 = target  
S1 + S2 = sum  
-----------------  
2S1 = target + sum  
S1 = (target + sum)/2

So the problem reduces to: Count the number of subsets with sum = (target + sum) / 2

If (target + sum) is odd or target > sum, return 0.

Step 1: Recursion

Choice Diagram

At every index i, we have two choices:

Pick nums[i] if it does not exceed the target.
Not pick nums[i].

IBH (Induction – Base – Hypothesis)

Function Signature:

int countWays(int index, int target, int[] nums)

Base Case:

If index == 0:
- If target == 0 and nums[0] == 0: return 2 (pick or not pick 0)
- If target == 0 or target == nums[0]: return 1
- Else return 0

Recurrence Relation:

int notPick = countWays(i-1, target, nums);
int pick = 0;
if(nums[i] <= target)
    pick = countWays(i-1, target - nums[i], nums);
return pick + notPick;

Code – Recursion:

class Solution {
    public int countWays(int index, int target, int[] nums) {
        if (index == 0) {
            if (target == 0 && nums[0] == 0) return 2;
            if (target == 0 || target == nums[0]) return 1;
            return 0;
        }

        int notPick = countWays(index - 1, target, nums);
        int pick = 0;
        if (nums[index] <= target)
            pick = countWays(index - 1, target - nums[index], nums);

        return pick + notPick;
    }

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

        if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0;

        int S1 = (sum + target) / 2;
        return countWays(nums.length - 1, S1, nums);
    }
}

Step 2: Memoization (Top-Down DP)

Add a dp[i][target] array to store already computed results.

Code – Memoization:

class Solution {
    public int countWays(int index, int target, int[] nums, int[][] dp) {
        if (index == 0) {
            if (target == 0 && nums[0] == 0) return 2;
            if (target == 0 || target == nums[0]) return 1;
            return 0;
        }

        if (dp[index][target] != -1) return dp[index][target];

        int notPick = countWays(index - 1, target, nums, dp);
        int pick = 0;
        if (nums[index] <= target)
            pick = countWays(index - 1, target - nums[index], nums, dp);

        return dp[index][target] = pick + notPick;
    }

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

        if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0;

        int S1 = (sum + target) / 2;
        int[][] dp = new int[nums.length][S1 + 1];
        for (int[] row : dp) Arrays.fill(row, -1);

        return countWays(nums.length - 1, S1, nums, dp);
    }
}

Step 3: Tabulation (Bottom-Up DP)

Code – Tabulation:

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

        if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0;

        int S1 = (sum + target) / 2;
        int n = nums.length;
        int[][] dp = new int[n][S1 + 1];

        // Base cases
        if (nums[0] == 0) dp[0][0] = 2; // +0 and -0
        else dp[0][0] = 1;

        if (nums[0] != 0 && nums[0] <= S1)
            dp[0][nums[0]] = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= S1; j++) {
                int notPick = dp[i - 1][j];
                int pick = 0;
                if (nums[i] <= j)
                    pick = dp[i - 1][j - nums[i]];
                dp[i][j] = pick + notPick;
            }
        }

        return dp[n - 1][S1];
    }
}

Step 4: Space Optimization

We only need values from the previous row → Use two 1D arrays.

Code – Space Optimized:

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

        if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0;

        int S1 = (sum + target) / 2;
        int n = nums.length;
        int[] prev = new int[S1 + 1];

        // Base case
        if (nums[0] == 0) prev[0] = 2;
        else prev[0] = 1;

        if (nums[0] != 0 && nums[0] <= S1)
            prev[nums[0]] = 1;

        for (int i = 1; i < n; i++) {
            int[] curr = new int[S1 + 1];
            for (int j = 0; j <= S1; j++) {
                int notPick = prev[j];
                int pick = 0;
                if (nums[i] <= j)
                    pick = prev[j - nums[i]];
                curr[j] = pick + notPick;
            }
            prev = curr;
        }

        return prev[S1];
    }
}

Time and Space Complexity

Time Complexity:
- Recursion: O(2^n)
- Memoization: O(n * target)
- Tabulation: O(n * target)
- Space Optimized: O(target)
Space Complexity:
- Recursion: O(n) stack
- Memoization: O(n * target)
- Tabulation: O(n * target)
- Space Optimized: O(target)

Conclusion

This problem is a disguised variation of subset sum count and emphasizes how transforming the problem using mathematical properties simplifies the logic significantly. You should always look for such transformations in DP problems.