# 494. Target Sum from collections import Counter """ given an integer array 'nums' and an integer 'target'. you want to buildan expression out of numbers by adding oneof the symbols '+' and '-' before each integer in nums awnd then concatenate all the integers. for example if 'nums = [2,1]', you can adda '+' before '2' and '-' before '1' and concatenate them to build the expression '+2-1'. return the number of different expressionsthat you can build, which evaluates to 'target'. """ class Solution(object): def findTargetSumWays(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ cnt = Counter({0: 1}) for x in nums: step = Counter() for y in cnt: step[y + x] += cnt[y] step[y - x] += cnt[y] cnt = step return cnt[target] if __name__ == "__main__": obj = Solution() print(obj.findTargetSumWays(nums=[1, 1, 1, 1, 1], target=3)) print(obj.findTargetSumWays(nums=[1], target=1))