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]What to watch: on the small input nums = [2, 3, 5] (target = 5), j sweeps leftward from target down to num, and a reachable cell at j - num flips dp[j] to true.
Numbers
init -- no cell examined yet
dp -- reachable sums
j sweeps leftward
Total is 10, so target is 5. Only sum 0 is reachable at the start, because the empty subset picks no numbers.
The last 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).