Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Two equal parts must each sum to half the total. Once we find a subset with that sum, all remaining elements automatically form the other half. The key is to track achievable sums while ensuring each array element is used at most once.

Approach

Reject an odd total and otherwise set the target to half the total. Initialize the reachable-sum set with zero for the empty subset.
For each element, build a separate set containing every old reachable sum plus that element. Return true immediately if one equals the target.
Merge the new sums into the old set, preserving choices that omit the element. Keeping the generation step separate prevents reusing the same element repeatedly.
After all elements, test whether the target is reachable. The reference code retains sums above the target as well; those states are unnecessary for success but do not affect correctness.

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

        target = total // 2
        seen = set()
        seen.add(0)

        for n in nums:
            new = set()
            for s in seen:
                if s + n == target:
                    return True
                new.add(s + n)
            seen = seen | new

        return target in seen

Complexity analysis

Let n = nums.length and T = sum(nums) / 2. The implementations do not prune above T, so reachable sums lie in [0, 2T]; the set-based DP still uses O(nT) time and O(T) auxiliary space.