Target Sum

Problem Id: 494 Difficulty: Medium


Intuition

Solution


class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        s = sum(nums)
        targets = {-s:1}
        for num in nums:
            new = {(k + 2 * num): v for k, v in targets.items()}
            for k in new:
                if k in targets:
                    targets[k] += new[k]
                else:
                    targets[k] = new[k]
        return targets.get(S, 0)