Skip to content

494. Target Sum

Array Dynamic Programming Backtracking

Problem - Target Sum

Medium

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_val = sum(nums)
        if sum_val < target or (sum_val - target) % 2:
            return 0

        n = (sum_val - target) // 2
        dp = [0] * (n + 1)
        dp[0] = 1

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

        return dp[-1]

Submission Stats:

  • Runtime: 20 ms (91.05%)
  • Memory: 17.9 MB (89.39%)