LC-0416 Medium LeetCode

416. Partition Equal Subset Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 48% Topics: Array, Dynamic Programming

Reading material

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

Reference solution (spoiler · python)

# Time:  O(n * s), s is the sum of nums
# Space: O(s)

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = sum(nums)
        if s % 2:
            return False

        dp = [False] * (s/2 + 1)
        dp[0] = True
        for num in nums:
            for i in reversed(xrange(1, len(dp))):
                if num <= i:
                    dp[i] = dp[i] or dp[i - num]
        return dp[-1]

Solution from kamyu104/LeetCode-Solutions · MIT