Problem 58 · Dynamic Programming

Partition Equal Subset Sum

MediumClassic DSA & systems

01Problem

Given an array of positive integers, return whether it can be split into two subsets with equal sums.

02Key insight

Reduces to 0/1 subset-sum targeting total/2. A Python int used as a bitset (reach |= reach << x) does the whole DP row in one word-parallel shift.

03Solution

solution.pypython9 lines

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reach = 1  # bit i set => sum i achievable
    for x in nums:
        reach |= reach << x
    return bool(reach >> target & 1)

Try it first.

TimeO(n * sum / w) with w-bit words

SpaceO(sum)

tests.py · 4 passing

tests.pypython4 lines

assert can_partition([1,5,11,5]) is True
assert can_partition([1,2,3,5]) is False
assert can_partition([2,2]) is True
assert can_partition([1]) is False

04Staff-level follow-up

Sum is huge but n is small (~40)? Switch to meet-in-the-middle: enumerate subset sums of each half (2^20) and match with sort + two pointers.