Target Sum (DP)

Fluffy seats only in Pincushion protea! © Diane Khambu

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

• 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 expression that you can build, which evaluates to target .

For recursion, the base case would be if we have length of nums array is equal to 1 and target is equal to nums[0]. That would gives us 1 way otherwise 0 way. We’ll aim towards reaching the base case using both + and — operation and return the sum to check if it equals to the target.

Here’s the implementation:

from typing import List

def find_target_sum_ways_helper(nums: List[int], idx: int, sum_so_far: int) -> int:
    if idx == len(nums) and sum_so_far == 0:
        return 1
    elif idx == len(nums) and sum_so_far != 0:
        return 0
    else:
        add_res = find_target_sum_ways_helper(nums, idx+1, sum_so_far + nums[idx])
        sub_res = find_target_sum_ways_helper(nums, idx+1, sum_so_far - nums[idx])
        return add_res + sub_res

def find_target_sum_ways(nums: List[int], target: int) -> int:
    return find_target_sum_ways_helper(nums, 0, target)


nums = [1, 1, 1, 1, 1]
target = 3
print(find_target_sum_ways(nums, target))  # prints 5

nums2 = [1]
target2 = 1
print(find_target_sum_ways(nums2, target2))  # prints 1

We are iterating over elements in nums array using idx and + and — ing each element from the target till idx is equal to the length of the array.

We return the sum of results got from both + ing and — ing each element.

Here’s how the recursion tree looks like for nums = [1, 1, 1, 1, 1] and target = 3 :

Recursion Tree for Target Sum Problem

Since there are 5 elements in nums array and two, + , — , operations, we have 2⁵ = 32 recursions! We know there are many repetitive computation, so let’s use cache to use the already computed values.

Here’s a memoized implementation:

from typing import List, Dict, Tuple
from collections import defaultdict

def find_target_sum_ways_helper(nums: List[int], memo: Dict[Tuple[int, int], int], \
                               idx: int, sum_so_far: int) -> int:
    if idx == len(nums) and sum_so_far == 0:
        return 1
    elif idx == len(nums) and sum_so_far != 0:
        return 0
    elif (idx, sum_so_far) in memo:  # caching based on index and sum
        return memo[(idx, sum_so_far)]
    else:
        add_res = find_target_sum_ways_helper(nums, memo, idx+1, sum_so_far + nums[idx])
        sub_res = find_target_sum_ways_helper(nums, memo, idx+1, sum_so_far - nums[idx])
        memo[(idx, sum_so_far)] = add_res + sub_res
        
        return memo[(idx, sum_so_far)]

def find_target_sum_ways(nums: List[int], target: int) -> int:
    memo = defaultdict(int)
    return find_target_sum_ways_helper(nums, memo, 0, target)


nums = [1, 1, 1, 1, 1]
target = 3
print(find_target_sum_ways(nums, target))  # prints 5

nums2 = [1]
target2 = 1
print(find_target_sum_ways(nums2, target2)) # prints 1

Wooho!

Now is Dynamic Programming (DP) way of implementation. In DP, two things to remember is use to recognize the subproblem and using the subproblem’s solution to build target’s solution.

For an array with 1 element and target of that element’s value for both + and — operation can be achieved in 1 way. Now let’s take into account target ranging from [-sum(nums) , sum(nums)] inclusive. For the range, if the value in range and + and — the element’s value falls within the range, we take the result.

Here’s an implementation:

from typing import List

def find_target_sum_ways(nums: List[int], target: int) -> int:
    max_sum = sum(abs(num) for num in nums)

    if target < -max_sum or target > max_sum:
        return 0

    ways = 2*max_sum + 1
    dp = [[0 for _ in range(ways)] for _ in range(len(nums))]

    dp[0][nums[0]] = 1  # for a nums list with 1 element, target 
    # equals to nums[0] and + operation
    dp[0][-nums[0]] = 1  # for a nums list with 1 element, target 
    # equals to -nums[0] and - operation

    # print(dp)

    for i in range(1, len(nums)):
        for s in range(-max_sum, max_sum+1):
            add_res = 0
            sub_res = 0

            if -max_sum <= s + nums[i] <= max_sum: # check if + operation falls withing range
                add_res = dp[i-1][s+nums[i]]

            if -max_sum <= s - nums[i] <= max_sum:  # check if - operation falls withing range
                sub_res = dp[i-1][s-nums[i]]

            dp[i][s] = max(dp[i][s], add_res + sub_res)

    return dp[-1][target]

nums = [1, 1, 1, 1, 1]
target = 3
print(find_target_sum_ways(nums, target))  # prints 5

nums2 = [1]
target2 = 1
print(find_target_sum_ways(nums2, target2)) # prints 1

There it is! This DP needed to take into consideration both the addition and subtraction of elements like in knapsack or other DP problem where we either include or do not include an element.

That’s all for this post. Congratulations on coming this far! 🎈

See you in my next post. Until then, ✨.

Inspirations:

• Leetcode

You can support me on Patreon!