leetcode

Target Sum

Target Sum

gap version - 232ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        count = {0: 1}
        for x in nums:
          count2 = {}
          for tmpSum in count:
            # print(x, tmpSum)
            count2[tmpSum + x] = count2.get(tmpSum + x, 0) + count[tmpSum]
            count2[tmpSum - x] = count2.get(tmpSum - x, 0) + count[tmpSum]
          count = count2
        return count.get(S, 0)

test code

1
2
In [57]: s = Solution(); t = s.findTargetSumWays([1,1,1,1,1], 3); print(t)
5

leet code