Target Sum

Problem

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Solution

Approach 1: Dynamic Programming (Subset Sum)

The key insight is to transform this into a subset sum problem. If we assign ‘+’ to subset P and ‘-‘ to subset N:

sum(P) - sum(N) = target
sum(P) + sum(N) = sum(nums)
Therefore: sum(P) = (target + sum(nums)) / 2

Implementation

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)

        # Check if solution is possible
        if total < abs(target) or (total + target) % 2 != 0:
            return 0

        # Find subset that sums to this value
        subset_sum = (total + target) // 2

        # DP: count ways to make each sum
        dp = [0] * (subset_sum + 1)
        dp[0] = 1  # One way to make 0: select nothing

        for num in nums:
            for s in range(subset_sum, num - 1, -1):
                dp[s] += dp[s - num]

        return dp[subset_sum]

Approach 2: 2D DP (Traditional)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)

        if total < abs(target) or (total + target) % 2 != 0:
            return 0

        subset_sum = (total + target) // 2
        n = len(nums)

        dp = [[0] * (subset_sum + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for s in range(subset_sum + 1):
                # Don't include nums[i-1]
                dp[i][s] = dp[i-1][s]

                # Include nums[i-1]
                if s >= nums[i-1]:
                    dp[i][s] += dp[i-1][s - nums[i-1]]

        return dp[n][subset_sum]

Approach 3: Recursion with Memoization

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        memo = {}

        def dp(i, current_sum):
            if i == len(nums):
                return 1 if current_sum == target else 0

            if (i, current_sum) in memo:
                return memo[(i, current_sum)]

            # Try adding + or - before nums[i]
            positive = dp(i + 1, current_sum + nums[i])
            negative = dp(i + 1, current_sum - nums[i])

            memo[(i, current_sum)] = positive + negative
            return memo[(i, current_sum)]

        return dp(0, 0)

Complexity Analysis

DP Subset Sum:

Time Complexity: O(n * sum), where n is array length and sum is the subset sum value.
Space Complexity: O(sum) for 1D DP array.

Recursive Memoization:

Time Complexity: O(n * total_range), where total_range is the range of possible sums.
Space Complexity: O(n * total_range) for memoization.

Key Insights

Transform to Subset Sum: The problem can be transformed into finding a subset with a specific sum.
Mathematical Reduction:
- Partition nums into P (positive) and N (negative)
- sum(P) - sum(N) = target
- sum(P) + sum(N) = total
- Solve: sum(P) = (target + total) / 2
Feasibility Check: If (target + total) is odd or total < target , no solution exists.
0/1 Knapsack: Each number can be used exactly once, making this a 0/1 knapsack variant.
Reverse Iteration: In 1D DP, iterate backwards to avoid using the same element twice.
Count Ways: Instead of finding if subset exists, we count all ways to achieve the subset sum.