The tell: Split into two equal halves — a subset-sum question in disguise.
How you get there
1An odd total cannot split evenly, so return early.
2Otherwise ask whether any subset sums to total // 2.
3A boolean 0/1 knapsack over that target answers it; iterate the target descending so each item is used once.
Solution
Python
def can_partition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for t in range(target, x - 1, -1): # descending: each item used at most once
dp[t] = dp[t] or dp[t - x]
return dp[target]
Time
O(n · sum)
Space
O(sum)
What goes wrong
Iterating the target ascending turns it into unbounded knapsack, reusing the same number repeatedly.