Partition Equal Subset Sum

House Robber III

Unique Paths II

Decide whether an array can be split into two subsets with equal sums.

Given an integer array `nums`, return `true` if you can split it into two subsets whose sums are equal, or `false` otherwise. Every element must belong to exactly one of the two subsets.

**Input / output**
- Input: `nums: int[]`
- Output: `boolean`

**Examples**
1. `nums = [1,5,11,5]` returns `true` because `[1,5,5]` and `[11]` both sum to `11`.
2. `nums = [1,2,3,5]` returns `false`; no split gives two equal halves.
3. `nums = [1,1]` returns `true`.

**Constraints**
- `1 <= nums.length <= 200`
- `1 <= nums[i] <= 100`

**Follow-up**
Notice that if the total is odd the answer is immediately `false`. Once you target `sum / 2`, why is it safe to iterate the inner sums from high to low with a single boolean row?

- Splitting into two equal halves means finding a subset that sums to exactly `total / 2`.
- If `total` is odd, no such subset exists, so return `false` immediately.
- Otherwise the question becomes: can any subset reach `target = total / 2`?

Reduce to subset sum

- Let `dp[i][s]` be `true` when some subset of the first `i` values sums to `s`.
- A sum of `0` is always reachable with the empty subset.
- Each value is either skipped (`dp[i-1][s]`) or taken (`dp[i-1][s - nums[i-1]]`).

Fill a 2D reachability table

- Each row only reads the row directly above, so a single boolean array of size `target + 1` suffices.
- Iterate the inner `sum` from high down to `value`; going downward guarantees each number is used at most once (a 0/1 knapsack, not unbounded).

Compress to one boolean row

- Start with `dp[0] = true`.
- For every value, mark `dp[sum]` reachable whenever `dp[sum - value]` was already reachable, scanning sums downward.
- The answer is `dp[target]`.

Optimal 1D solution

Trace `nums = [1,5,11,5]`, `target = 11`.

- Start: reachable sums `{0}`.
- After `1`: `{0,1}`.
- After `5`: `{0,1,5,6}`.
- After `11`: `{0,1,5,6,11,...}` — `11` is now reachable, so the answer is `true`.

Dry run

- Iterating the inner sum upward, which reuses the same element multiple times and turns it into unbounded knapsack.
- Forgetting the odd-total shortcut, or comparing against `total` instead of `total / 2`.
- Allocating `dp` of size `target` instead of `target + 1` and missing the exact-target cell.
- Follow-up: how would you recover the actual subset, not just whether one exists?

Common mistakes and follow-ups

- A single element can never be split, so the answer is `false`.
- An odd total is always `false`.
- Two equal elements are always `true`.

Edge cases to test mentally

Target half the total and fill a 1D subset-sum table, scanning sums downward per value. Time is `O(n * sum)` and extra space is `O(sum)`.