Hints — p61 Partition Equal Subset Sum

Hint 1. Equal partition means each side sums to total/2. If total is odd, impossible. Otherwise the question is: “is there a subset summing to total/2?”

Hint 2. That’s classic subset-sum. Define dp[s] = True if some subset of the items considered so far sums to s. Initialize dp[0] = True (empty subset).

Hint 3. For each item x, update: dp[s] = dp[s] OR dp[s - x] for each s. Walk s backwards from target down to x — forward iteration lets you reuse x, which is unbounded knapsack, wrong here.

Hint 4. Time O(n·S), space O(S) where S = total/2. LC 416 caps S to 10000 so this fits comfortably.

Hint 5. Slick Pythonic version: represent dp as a Python bigint. dp |= dp << x updates all sums in one shift-or. Final check: (dp >> target) & 1. ~64× faster.

If stuck: see solution.py.