494 Target Sum

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:

• The length of the given array is positive and will not exceed 20.

• The sum of elements in the given array will not exceed 1000.

• Your output answer is guaranteed to be fitted in a 32-bit integer.

Brute Force:

The Idea: Before we can understand the dynammic approach, I like to lay down the solution first using brute force. This allows me to see the entire structure on it's own so I can then identify patterns and substructures. Using DFS, we can explore all possible operators on the array. The structure for array [1,5,1], S=5 is shown below. The children are defined as the + or - sum from the parent. Any time we reach a leaf (summed all the elements of the array) and the sum is the target, then we can increment our solution by 1.

Complexity: O(2^N) time and O(N) space

import operator


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

        root = {'sum':0, 'iter':-1}
        sol = [0]

        def dfs(node, op):
            next_iter = node['iter'] + 1
            if next_iter >= len(nums):
                return
            else:
                target_num = nums[next_iter]
                next_sum = op(node['sum'], target_num)
                if next_sum is S and next_iter + 1 >= len(nums):
                    sol[0] += 1

                dfs({'sum': next_sum, 'iter': next_iter}, operator.add)
                dfs({'sum': next_sum, 'iter': next_iter}, operator.sub)

        dfs(root, operator.add)
        dfs(root, operator.sub)
        return sol[0]

Dynammic Programming:

The Idea: Looking the image above, we can identify some substructures. First, the trees are vertical mirrors images of one another. Knowing this, we can then just recurse on the positive part from the root, and if we identify a -S, we also add it to our solution, since it is going to be mirrored on the other end anyway. The special case here begin when S is 0, but that can be easily accounted for. The next thing to look at is overlapping substructure. We know that if we have an identical number on the same level, then we know that it is going to eventually lead to the same sum. So if we hash by the current sum and the level (iterator in the array), then we can make this check before we explore further down into the tree.

Complexity:

import operator


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

        sol = [0]
        def dfs(node, op):
            next_iter = node['iter'] + 1
            if next_iter >= len(nums):
                return
            else:
                target_num = nums[next_iter]
                next_sum = op(node['sum'], target_num)
                if (next_sum == S or next_sum == -S) \
                        and next_iter + 1 >= len(nums):
                    sol[0] += 1

                dfs({'sum': next_sum, 'iter': next_iter}, operator.add)
                dfs({'sum': next_sum, 'iter': next_iter}, operator.sub)


        dfs({'sum':0, 'iter':-1}, operator.add)
        if S == 0:
            sol[0] *= 2
        return sol[0]



obj = Solution()
print(obj.findTargetSumWays([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 0)) # 2^20
print(obj.findTargetSumWays([1000], 1000)) # 1
print(obj.findTargetSumWays([1,2,1], 0)) # 2: (-1,2,-1) and (1,-2,1)
print(obj.findTargetSumWays([1, 2, 3, 4, 5, 6, 7, 8, 9], 5)) # 22
print(obj.findTargetSumWays([1, 5, 1], 5)) # 2
print(obj.findTargetSumWays([1, 1, 1, 1, 1], 3)) # 5