494. Target Sum

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

Approach 01:

#include <vector>
#include <numeric>
using namespace std;

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

        // Check if the targetSum is achievable
        if (totalSum < abs(targetSum) || (totalSum + targetSum) % 2 == 1) {
            return 0;
        }

        int subsetSum = (totalSum + targetSum) / 2;
        return knapsack(numbers, subsetSum, totalSum);
    }

private:
    int knapsack(const vector<int>& numbers, int subsetSum, int totalSum) {
        // dp[i]: Number of ways to sum to i using numbers so far
        vector<int> dp(totalSum + 1, 0);
        dp[0] = 1;

        for (int num : numbers) {
            for (int j = totalSum; j >= num; --j) {
                dp[j] += dp[j - num];
            }
        }

        return dp[subsetSum];
    }
};

class Solution:
    def findTargetSumWays(self, numbers: list[int], targetSum: int) -> int:
        totalSum = sum(numbers)

        # Check if the targetSum is achievable
        if totalSum < abs(targetSum) or (totalSum + targetSum) % 2 == 1:
            return 0

        def knapsack(subsetSum: int) -> int:
            # dp[i]: Number of ways to sum to i using numbers so far
            dp = [1] + [0] * totalSum

            for num in numbers:
                for j in range(totalSum, num - 1, -1):
                    dp[j] += dp[j - num]

            return dp[subsetSum]

        subsetSum = (totalSum + targetSum) // 2
        return knapsack(subsetSum)

Time Complexity

• Preprocessing:
  • The calculation of the total sum using the accumulate function takes \( O(n) \), where \( n \) is the size of the array.
• Dynamic Programming:
  • The outer loop iterates over all elements in the array, i.e., \( O(n) \).
  • The inner loop iterates over all possible subset sums from \( subsetSum \) down to 0, resulting in a total of \( O(n \times subsetSum) \).
• Overall Time Complexity:

  The total time complexity is: \( O(n \times subsetSum) \).

Space Complexity

• Dynamic Programming Array:
  • The DP array has a size of \( totalSum + 1 \), requiring \( O(totalSum) \) space.
• Auxiliary Variables:
  • Additional variables such as totalSum, subsetSum, and loop variables use \( O(1) \) space.
• Overall Space Complexity:

  The total space complexity is: \( O(totalSum) \).