Given an array of positive integers, the machine must decide whether the array can be split into two subsets whose sums are equal. Each element is used in exactly one of the two sides, and the elements themselves are not reordered — the problem is pure subset selection.
The key insight is the reduction to subset sum: two equal-sum subsets both sum to total / 2, so the machine only needs to find any subset summing to exactly half the total. If the total is odd, an equal split is arithmetically impossible and the machine can return false without doing any work.
The approach runs in three steps. First, compute the total and immediately reject odd totals; also reject when any single element exceeds the target. Second, maintain a boolean dp table where dp[t] records whether some subset of the elements seen so far sums to t, and walk the array descending through the table so each element is used at most once. Third, return dp[target]. Time is O(n x target) and space is O(target).
The trickiest edge case is exactly-half reachability with large elements: a number bigger than the target can never participate, and iterating the table from high to low is what keeps the 0/1 constraint — a low-to-high sweep would let the machine reuse the same element and produce false positives.
def canPartition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for t in range(target, num - 1, -1):
dp[t] = dp[t] or dp[t - num]
return dp[target]