0494 Target Sum

0494 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.

Examples#

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

Constraint#

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

Analysis#

This is a complete knapsack problem, which can be solved using

  • backtracking

    • duplicated subproblems

  • dynamic programming

Solution#

Backtrack#

Backtrack generates a complete search tree, which leads to the time complexity of \(O(2^{len(nums)})\).

# use backtracking to solve the complete knapsack problem
def targetSum(nums, target):
    # define a result
    res = 0

    # define a backtrack function that returns the number of ways to assign symbols to make sum of nums equal to target for given first i elements and a current sum
    def backtrack(i, curr_sum):
        nonlocal res
        # base case: if we have reached the end of the nums
        # return +1 if the curr_sum is equal to target, skip otherwise
        if i == len(nums):
            res += 1 if curr_sum == target else 0
            return

        # backtrack(path, choices)
        choices = [-nums[i], nums[i]]
        for choice in choices:
            # make a choice
            curr_sum += choice
            # backtrack
            backtrack(i+1, curr_sum)
            # undo the choice
            curr_sum -= choice 
    
    backtrack(0, 0)
    return res

# test
# 5
nums = [1, 1, 1, 1, 1]
target = 3
print(targetSum(nums, target))

# 1
nums = [1]
target = 1
print(targetSum(nums, target))

5
1

Dynamic Programming#

# dp function: 
def targetSum(nums, target):

    # dp function: dp[i][j] represents the number of ways to assign symbols to make sum of nums equal to j for given first i elements
    # i = 0 means no element
    # i = 1 means the first element
    def dp(i, remain):
        # base case
        if i == 0:
            return 1 if remain == 0 else 0

        return dp(i-1, remain-nums[i-1]) + dp(i-1, remain+nums[i-1])
    
    return dp(len(nums), target)

# test
# 5
nums = [1, 1, 1, 1, 1]
target = 3
print(targetSum(nums, target))

# 1
nums = [1]
target = 1
print(targetSum(nums, target))

5
1

# DP Function with memo
def targetSum(nums, target):
    memo = {}

    def dp(i, remain):
        # base
        if i == 0:
            return 1 if remain == 0 else 0

        # if in memo
        if (i, remain) in memo:
            return memo[(i, remain)]

        # if not, then update memo: "+nums[i-1]" and "-nums[i-1]"
        memo[(i, remain)] = dp(i-1, remain - nums[i-1]) + dp(i-1, remain + nums[i-1])

        return memo[(i, remain)]
    
    return dp(len(nums), target)

# test
# 5
nums = [1, 1, 1, 1, 1]
target = 3
print(targetSum(nums, target))

# 1
nums = [1]
target = 1
print(targetSum(nums, target))

5
1
Contents