494.Target Sum

Tags: [dp], [top_to_bottom_dp], [recursion], [state]

Com: {fb}

Link: https://leetcode.com/problems/target-sum/\#/description

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols+and-. For each integer, you should choose one from+and-as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input:
 nums is [1, 1, 1, 1, 1], S is 3. 

Output:
 5

Explanation:
-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

Solution: DP, Top To Bottom DP

class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if not nums:
            return 0

        memo = {}
        return self.find_target_sum_ways_helper(nums, 0, S, 0, memo)

    def find_target_sum_ways_helper(self, nums, index, S, tmp_result, memo):
        # base case
        if index >= len(nums):
            if tmp_result == S:
                return 1
            return 0

        state = '{}->{}'.format(index, tmp_result)
        if state in memo:
            return memo[state]

        result = 0
        # choice one: using '+' sign
        result += self.find_target_sum_ways_helper(nums, index + 1, S, tmp_result + nums[index], memo)

        # choice two: using '-' sign
        result += self.find_target_sum_ways_helper(nums, index + 1, S, tmp_result - nums[index], memo)

        memo[state] = result
        return result

Revelation:

• Most of time, we don't need use a global variable to accumulate the data, such as self.counter. We can convert it to that if find the target return 1, otherwise return 0, then in the body of the recursion sum all cases responses together, then return the sum value.
• There exists overlapping computation here, think about that the given nums = [1, 1, 1, 1, 1, 1], and the current index = 2, if the tmp_result = 0, there are two cases to make the tmp_result = 0, one is 1 -1, the other is -1 1, and both cases need to compute the remaining part of the array, which means from this point, these two cases will overlapping compute the remaining part of the array. So we can apply the DP on this problem.
• The state of memo is 'index->tmpresult', because these two data can identify the current state for the remaining computation. Only using index or tmpresult as the state is not enough.

Note:

• Time compute = O(n * (2 * sum(array))), n is the number of elements of the given nums. The range of tmp_result = [-sum(array), sum(array)].