@@ -0,0 +1,1349 @@
+# Time:  O(n * S)%0A# Space: O(S)%0A%0A# You are given a list of non-negative integers, a1, a2, ..., an,%0A# and a target, S. Now you have 2 symbols + and -.%0A# For each integer, you should choose one from + and - as its new symbol.%0A#%0A# Find out how many ways to assign symbols to make sum of integers equal to target S.%0A#%0A# Example 1:%0A# Input: nums is %5B1, 1, 1, 1, 1%5D, S is 3. %0A# Output: 5%0A# Explanation: %0A#%0A# -1+1+1+1+1 = 3%0A# +1-1+1+1+1 = 3%0A# +1+1-1+1+1 = 3%0A# +1+1+1-1+1 = 3%0A# +1+1+1+1-1 = 3%0A#%0A# There are 5 ways to assign symbols to make the sum of nums be target 3.%0A# Note:%0A# The length of the given array is positive and will not exceed 20.%0A# The sum of elements in the given array will not exceed 1000.%0A# Your output answer is guaranteed to be fitted in a 32-bit integer.%0A%0Aclass Solution(object):%0A    def findTargetSumWays(self, nums, S):%0A        %22%22%22%0A        :type nums: List%5Bint%5D%0A        :type S: int%0A        :rtype: int%0A        %22%22%22%0A        def subsetSum(nums, S):%0A            dp = collections.defaultdict(int)%0A            dp%5B0%5D = 1%0A            for n in nums:%0A                for i in reversed(xrange(n, S+1)):%0A                    if i-n in dp:%0A                        dp%5Bi%5D += dp%5Bi-n%5D%0A            return dp%5BS%5D%0A%0A        total = sum(nums)%0A        if total %3C S or (S + total) %25 2: return 0%0A        P = (S + total) // 2%0A        return subsetSum(nums, P)%0A

Create target-sum.py