Target Sum

Problem Description

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

You want to build an expression using all the integers in nums by assigning either a '+' or '-' sign before each integer and then concatenate them all to evaluate the expression.

• 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" which evaluates to 1.

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

Examples

Constraints

• 1 ≤ nums.length ≤ 20
• 0 ≤ nums[i] ≤ 1000
• 0 ≤ sum(nums[i]) ≤ 1000
• -1000 ≤ target ≤ 1000

Mathematical Reduction to Subset Sum

Let the sum of all elements assigned a '+' sign be P, and the sum of all elements assigned a '-' sign be N. We have:

1. P - N = target
2. P + N = totalSum

Adding these equations: 2 * P = target + totalSum => P = (target + totalSum) / 2

Thus, the problem reduces to finding the number of subsets of nums that sum to exactly P = (target + totalSum) / 2.

Constraints and Invalidity:

• If target + totalSum is odd, or if target + totalSum < 0, no valid integer subset sum P can exist. Return 0.

Solution: 1D DP Array

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

        // mathematically impossible check
        if ((target + totalSum) % 2 != 0 || target + totalSum < 0) {
            return 0;
        }

        int subsetTarget = (target + totalSum) / 2;
        int[] dp = new int[subsetTarget + 1];
        dp[0] = 1;

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

        return dp[subsetTarget];
    }
}

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        total_sum = sum(nums)
        
        # mathematically impossible check
        if (target + total_sum) % 2 != 0 or target + total_sum < 0:
            return 0

        subset_target = (target + total_sum) // 2
        dp = [0] * (subset_target + 1)
        dp[0] = 1

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

        return dp[subset_target]

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

class Solution {
public:
    int findTargetSumWays(std::vector<int>& nums, int target) {
        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);

        if ((target + totalSum) % 2 != 0 || target + totalSum < 0) {
            return 0;
        }

        int subsetTarget = (target + totalSum) / 2;
        std::vector<int> dp(subsetTarget + 1, 0);
        dp[0] = 1;

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

        return dp[subsetTarget];
    }
};

Complexity Analysis:

• Time Complexity: O(N * T) where N is the length of nums and T is the subsetTarget sum. Given constraints, N ≤ 20 and T ≤ 1000. The nested loop executes at most 20 * 1000 = 20000 operations, making it extremely fast.
• Space Complexity: O(T) to store the 1D DP array.

← All Problems