# 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.
import collections


class Solution(object):
    # after see this test case, [1000], -1000
    # I begin to know my below solution is wrong, because dp[i][j], j could be negative
    def findTargetSumWays_wrong(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        # dp[i][j] : choose i num from nums, sum to j , how many ways to do it
        # dp[i][j-nums[i]] += dp[i-1][j] if we substract the nums[i]
        # dp[i][j+nums[i]] += dp[i-1][j], if we add nums[i]

        t, n = sum(nums) + 1, len(nums)
        if t <= S:
            return 0
        dp = [[0] * t for _ in xrange(n + 1)]

        for i in xrange(0, n):
            dp[i][0] = 1

        # dp[0][0] = 1

        for i in xrange(0, n):
            for j in xrange(0, t - nums[i]):
                dp[i + 1][j + nums[i]] += dp[i][j]
                if j >= nums[i]:
                    dp[i + 1][j - nums[i]] += dp[i][j]

        return dp[n][S]

    def findTargetSumWays2(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        # dp[i][j] : choose i num from nums, sum to j , how many ways to do it
        # dp[i][j-nums[i]] += dp[i-1][j] if we substract the nums[i]
        # dp[i][j+nums[i]] += dp[i-1][j], if we add nums[i]
        # because j could be negatvie, for test case [1000], -1000, so we can not use a 2-dim list
        # instead we could use map

        dp = collections.defaultdict(dict)
        n, t = len(nums), sum(nums)
        if t < abs(S):
            return 0

        for i in xrange(0, n + 1):
            for j in xrange(-t, t + 1):
                # bugfixed, I have to initialized the dictionary, otherwises, the below code would throw
                # KeyError. because dp[][] += count, but at that time, dp[][] is not exist yet
                dp[i][j] = 0

        dp[0][0] = 1

        for i in xrange(0, n):
            for s, count in dp[i].iteritems():
                # try to avoid KeyError by using `get`
                t = dp[i + 1].get(s + nums[i], 0)
                dp[i + 1][s + nums[i]] = t + count
                t = dp[i + 1].get(s - nums[i], 0)
                dp[i + 1][s - nums[i]] = t + count

        return dp[n][S]

    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """

        n, t = len(nums), sum(nums)
        dp = [collections.defaultdict(int)] * (n + 1)

        dp[0][0] = 1

        for i in xrange(0, n):
            # try to avoid KeyError by using `get`
            tmp = collections.defaultdict(int)
            for s, count in dp[i].iteritems():
                # workaround, because during iteraton, we can not change the entry of diction
                tmp[s + nums[i]] = tmp.get(s + nums[i], 0) + count
                tmp[s - nums[i]] = tmp.get(s - nums[i], 0) + count
            dp[i + 1] = tmp

        return dp[n].get(S, 0)

    def findTargetSumWays3(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        dp, n = {0: 1}, len(nums)


        for i in xrange(n):
            tmp = {}
            for s, c in dp.iteritems():
                tmp[s + nums[i]] = tmp.get(s + nums[i], 0) + c
                tmp[s - nums[i]] = tmp.get(s - nums[i], 0) + c
            dp = tmp

        return dp.get(S, 0)





if __name__ == '__main__':
    print Solution().findTargetSumWays([2, 7, 9, 13, 27, 31, 37, 3, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 47, 53], 37)
    print Solution().findTargetSumWays3([2, 7, 9, 13, 27, 31, 37, 3, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 47, 53], 37)
    print Solution().findTargetSumWays([1, 2, 7, 9, 981], 1000000000)
    print Solution().findTargetSumWays3([1, 2, 7, 9, 981], 1000000000)
    print Solution().findTargetSumWays([1], -1)
    print Solution().findTargetSumWays3([1], -1)
    print Solution().findTargetSumWays([1], 1)
    print Solution().findTargetSumWays3([1], 1)
    print Solution().findTargetSumWays([1], 2)
    print Solution().findTargetSumWays3([1], 2)
    print Solution().findTargetSumWays([1, 1, 1, 1, 1], 3)
    print Solution().findTargetSumWays3([1, 1, 1, 1, 1], 3)
