Medium

Partition Equal Subset Sum

089

Return true if nums can be split into two subsets with equal sum.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    5,
    11,
    5
  ]
}

Output
true

FUNCTION SHAPE

nums: intArray→bool

SOLUTION NOTE

If total is odd, impossible. Otherwise, find if any subset sums to total/2. Use take-or-don't-take pattern for each element.

Reveal reference solution +

pythonREFERENCE

def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0: return False
    target = total // 2

    @cache
    def dp(i, remaining):
        if remaining == 0: return True
        if i >= len(nums) or remaining < 0: return False
        return dp(i+1, remaining - nums[i]) or dp(i+1, remaining)

    return dp(0, target)

TimeO(n × sum)

SpaceO(n × sum)

Open on LeetCode ↗