MediumBlind75ArrayDP

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 '+' or '-' before each integer. Return the number of different expressions that evaluate to target.

Examples

Input
nums = [1,1,1,1,1], target = 3
Output
5

There are 5 ways: -1+1+1+1+1, 1-1+1+1+1, 1+1-1+1+1, 1+1+1-1+1, 1+1+1+1-1.

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

One expression: +1 = 1.

Constraints

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

Approaches

Try all 2^n sign combinations.

CodeT: O(2^n) | S: O(n)
def find_target_sum_ways(nums, target):
    def helper(i, remaining):
        if i == len(nums):
            return 1 if remaining == 0 else 0
        return helper(i + 1, remaining - nums[i]) + helper(i + 1, remaining + nums[i])
    return helper(0, target)

Use memoization to avoid recomputing subproblems.

CodeT: O(n * sum) | S: O(n * sum)
def find_target_sum_ways(nums, target):
    memo = {}
    def helper(i, remaining):
        if i == len(nums):
            return 1 if remaining == 0 else 0
        if (i, remaining) in memo:
            return memo[(i, remaining)]
        result = helper(i + 1, remaining - nums[i]) + helper(i + 1, remaining + nums[i])
        memo[(i, remaining)] = result
        return result
    return helper(0, target)

Convert to subset sum problem: find subset with sum = (sum + target) / 2.

Diagram

nums = [1,1,1,1,1], target = 3 sum=5, subset_sum = (5+3)/2 = 4 dp = [1,0,0,0,0] num=1: dp = [1,1,0,0,0] num=1: dp = [1,2,1,0,0] num=1: dp = [1,3,3,1,0] num=1: dp = [1,4,6,4,1] num=1: dp = [1,5,10,10,5] Result: dp[4] = 5
CodeT: O(n * subset_sum) | S: O(subset_sum)
def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (total + target) % 2 != 0 or total + target < 0:
        return 0
    subset_sum = (total + target) // 2
    dp = [0] * (subset_sum + 1)
    dp[0] = 1
    for num in nums:
        for j in range(subset_sum, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[subset_sum]

Complexity Comparison

Recursion
T: O(2^n)S: O(n)

Try all 2^n sign combinations.

DP - Memoization
T: O(n * sum)S: O(n * sum)

Use memoization to avoid recomputing subproblems.

DP - Knapsack
T: O(n * subset_sum)S: O(subset_sum)

Convert to subset sum problem: find subset with sum = (sum + target) / 2.

Common Mistakes

Using recursion without memoization (exponential time)

Not handling the case where the total sum + target is odd

Using 2D DP when 1D optimized DP is possible

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems