Return whether the array can be partitioned into two subsets with equal sums.
Before you code
That is the same as finding a subset summing to half the total. An odd total is an immediate no.
Hints
target = total // 2;dp[0] = True.- For each number x, for s from target down to x:
dp[s] = dp[s] or dp[s - x]. - The downward loop keeps each number used at most once.
Production & complexity notes
When solving Partition equal subset sum on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Knapsack and subsets to reinforce the underlying pattern.
What it practices
Subset sum as a boolean knapsack, from Knapsack and subsets.