Partition Equal Subset Sum

If the total sum is odd, an equal split is impossible immediately. Otherwise, the question “can this array split into two equal halves?” is the same as “can some subset of the array sum to exactly total / 2?” – because whatever that subset does not include automatically forms the other, equal-sum half. That reduces the problem to a classic 0/1 knapsack: is target = total / 2 a reachable subset sum?

Brute Force Recursion

Time O(2ⁿ)Space O(n)

For each number, recursively decide whether to include it in the “first half” subset or not, tracking the remaining amount needed to hit target.

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

        def canReach(i: int, remaining: int) -> bool:
            if remaining == 0:
                return True
            if i == len(nums) or remaining < 0:
                return False
            return canReach(i + 1, remaining - nums[i]) or canReach(i + 1, remaining)

        return canReach(0, target)

Each of the n numbers independently branches into “include” or “exclude” → O(2ⁿ) time, O(n) recursion depth.

Bottom-Up DP (0/1 Knapsack)

OptimalTime O(n · target)Space O(target)

Maintain a boolean array dp of size target + 1, where dp[j] means “sum j is reachable using numbers processed so far.” Start with only dp[0] = True (an empty subset sums to 0). For each number, update dp by scanning j from target down to num: if dp[j - num] was already reachable, then adding this number makes dp[j] reachable too. Scanning backward is essential – it stops each number from being used more than once.

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

        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            for j in range(target, num - 1, -1):
                if dp[j - num]:
                    dp[j] = True
                if dp[target]:
                    return True
        return dp[target]

Trace for nums = [1, 5, 11, 5] (target = 11); each step shows the full reachability array after folding in one number:

target = 11

1 / 4

seenresult

Initial state: only sum 0 is reachable (the empty subset).

The second 5 is never processed because the loop returns as soon as dp[target] flips true. Each of the n numbers scans up to target cells → O(n · target) time, O(target) space for the dp array (this is pseudo-polynomial: it depends on the numeric value of the sum, not just the array length).