# LeetCode 416: Partition Equal Subset Sum

## Problem Restatement

We are given an integer array `nums`.

Return `True` if we can split the array into two subsets such that both subsets have the same sum.

Otherwise, return `False`.

Each number can be used at most once, because every element belongs to exactly one of the two subsets.

The source problem gives examples such as `nums = [1,5,11,5]`, which returns `true`, and `nums = [1,2,3,5]`, which returns `false`. The constraints are `1 <= nums.length <= 200` and `1 <= nums[i] <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | `True` if the array can be split into two equal-sum subsets |
| Number usage | Each element can be used once |
| Subset rule | Subsets do not need to be contiguous |
| Values | Positive integers |

Example function shape:

```python
def canPartition(nums: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
nums = [1, 5, 11, 5]
```

The answer is:

```python
True
```

One valid partition is:

```text
[1, 5, 5] and [11]
```

Both subsets have sum:

```python
11
```

Example 2:

```python
nums = [1, 2, 3, 5]
```

The answer is:

```python
False
```

The total sum is:

```python
1 + 2 + 3 + 5 = 11
```

Since `11` is odd, it cannot be split into two equal integer sums.

## First Thought: Try Every Subset

A direct approach is to try every possible subset.

For each subset, compute its sum.

If any subset has sum equal to half of the total array sum, then the remaining elements automatically form the other half.

But there are:

```python
2^n
```

possible subsets.

With up to `200` numbers, this is too slow.

## Key Insight

If the total sum is odd, equal partition is impossible.

If the total sum is even, each subset must have sum:

```python
target = total_sum // 2
```

So the problem becomes:

Can we choose some numbers from `nums` whose sum is exactly `target`?

This is the classic 0/1 knapsack subset-sum problem.

Each number can be chosen once or skipped once.

## Dynamic Programming Idea

Let:

```python
dp[s]
```

mean:

Can we form sum `s` using the numbers processed so far?

Initially:

```python
dp[0] = True
```

because sum `0` can always be formed by choosing nothing.

For each number `num`, update possible sums.

If sum `s - num` was possible before using `num`, then sum `s` becomes possible after using `num`.

So:

```python
dp[s] = dp[s] or dp[s - num]
```

We must scan `s` backward from `target` down to `num`.

This prevents using the same number more than once.

## Algorithm

1. Compute the total sum.
2. If the total sum is odd, return `False`.
3. Set `target = total_sum // 2`.
4. Create a boolean array `dp` of size `target + 1`.
5. Set `dp[0] = True`.
6. For each `num` in `nums`:
   - For `s` from `target` down to `num`:
     - If `dp[s - num]` is true, set `dp[s] = True`.
7. Return `dp[target]`.

## Correctness

The dynamic programming invariant is:

After processing the first `i` numbers, `dp[s]` is true exactly when some subset of those first `i` numbers has sum `s`.

Before processing any number, only sum `0` is possible, so `dp[0] = True` is correct.

When processing a number `num`, each target sum `s` has two possibilities.

We can skip `num`, in which case `dp[s]` remains as it was.

Or we can use `num`, in which case we need a previous subset with sum `s - num`.

So the update:

```python
dp[s] = dp[s] or dp[s - num]
```

captures exactly these two choices.

The backward loop ensures `num` is used at most once. If we looped forward, `dp[s - num]` might already include the current `num`, causing repeated use.

After all numbers are processed, `dp[target]` is true exactly when some subset sums to half of the total sum.

If such a subset exists, the remaining numbers also sum to the same value. Therefore, the array can be partitioned into two equal-sum subsets.

If no such subset exists, no equal partition is possible.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * target)` | For each number, we scan sums up to `target` |
| Space | `O(target)` | We store one boolean array |

Here:

| Symbol | Meaning |
|---|---|
| `n` | Length of `nums` |
| `target` | `sum(nums) // 2` |

Given the constraints, `sum(nums)` is at most `200 * 100 = 20000`, so `target` is at most `10000`.

## Implementation

```python
from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)

        if total % 2 == 1:
            return False

        target = total // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            for s in range(target, num - 1, -1):
                dp[s] = dp[s] or dp[s - num]

            if dp[target]:
                return True

        return dp[target]
```

## Code Explanation

We compute the total sum:

```python
total = sum(nums)
```

If the total is odd:

```python
if total % 2 == 1:
    return False
```

then equal partition is impossible.

The target subset sum is:

```python
target = total // 2
```

The array:

```python
dp = [False] * (target + 1)
```

tracks which sums can be formed.

We set:

```python
dp[0] = True
```

because choosing no elements gives sum `0`.

For each number:

```python
for num in nums:
```

we update possible sums in reverse:

```python
for s in range(target, num - 1, -1):
```

The update:

```python
dp[s] = dp[s] or dp[s - num]
```

means sum `s` is possible if it was already possible, or if we can make `s - num` before adding `num`.

We can return early when `target` becomes possible:

```python
if dp[target]:
    return True
```

Finally:

```python
return dp[target]
```

returns whether half the total sum can be formed.

## Testing

```python
def test_can_partition():
    s = Solution()

    assert s.canPartition([1, 5, 11, 5]) is True
    assert s.canPartition([1, 2, 3, 5]) is False
    assert s.canPartition([1, 1]) is True
    assert s.canPartition([2, 2, 3, 5]) is False
    assert s.canPartition([100, 100]) is True
    assert s.canPartition([1, 2, 5]) is False
    assert s.canPartition([3, 3, 3, 4, 5]) is True

    print("all tests passed")
```

## Test Notes

| Test | Why |
|---|---|
| `[1,5,11,5]` | Standard reachable example |
| `[1,2,3,5]` | Odd total sum |
| `[1,1]` | Small successful partition |
| `[2,2,3,5]` | Even total but no half-sum subset |
| `[100,100]` | Large equal pair |
| `[1,2,5]` | Half sum exists numerically but cannot be formed |
| `[3,3,3,4,5]` | Multiple choices can form target |