LC-0494 Medium LeetCode

494. Target Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 51% Topics: Array, Dynamic Programming, Backtracking

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(n * S)
# Space: O(S)

import collections


class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        def subsetSum(nums, S):
            dp = collections.defaultdict(int)
            dp[0] = 1
            for n in nums:
                for i in reversed(xrange(n, S+1)):
                    if i-n in dp:
                        dp[i] += dp[i-n]
            return dp[S]

        total = sum(nums)
        if total < S or (S + total) % 2: return 0
        P = (S + total) // 2
        return subsetSum(nums, P)

Solution from kamyu104/LeetCode-Solutions · MIT