> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Partition Equal Subset Sum Python Solution

> Tested Python solution for LeetCode 416 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 416, Medium. Topics: Array, Dynamic Programming. [View on LeetCode](https://leetcode.com/problems/partition-equal-subset-sum/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 416   # by problem number
lcpy gen -s partition_equal_subset_sum   # by problem name
```

## Problem

Given an integer array `nums`, return `true` if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or `false` otherwise.

### Examples

```
Input: nums = [1,5,11,5]
Output: true
```

**Explanation:** The array can be partitioned as \[1, 5, 5] and \[11].

```
Input: nums = [1,2,3,5]
Output: false
```

**Explanation:** The array cannot be partitioned into equal sum subsets.

### Constraints

* 1 \<= nums.length \<= 200
* 1 \<= nums\[i] \<= 100

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/partition_equal_subset_sum/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/partition_equal_subset_sum/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n * sum)
    # Space: O(sum)
    def can_partition(self, nums: list[int]) -> bool:
        """
        Example: nums = [1, 5, 11, 5], target = 11

        Initial: dp = [T, F, F, F, F, F, F, F, F, F, F, F]
                      0  1  2  3  4  5  6  7  8  9 10 11

        After num=1: [T, T, F, F, F, F, F, F, F, F, F, F]
                      └─┘ (can make sum 1)

        After num=5: [T, T, F, F, F, T, T, F, F, F, F, F]
                      └─┘          └─┘ └─┘ (can make sums 5,6)

        After num=11:[T, T, F, F, F, T, T, F, F, F, F, T]
                                                        └─┘ (target!)

        Backward iteration prevents using same number twice
        """
        total = sum(nums)
        if total % 2:
            return False

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

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

            # Early termination: found target sum!
            if dp[target]:
                return True

        return False


class SolutionBitset:
    # Time: O(n * sum)
    # Space: O(1)
    def can_partition(self, nums: list[int]) -> bool:
        """
        Example: nums = [1, 5, 11, 5], target = 11

        Bitset representation (bit position = achievable sum):

        Initial:     dp = 1 (binary: 1)
                     Bits: ...0001
                     Sums: {0}

        After num=1: dp |= dp << 1
                     a = dp = 1 (bin: 0001)
                     b = dp << 1 = 2 (bin: 0010)
                     c = a | b = 3 (bin: 0011)
                     Sums: {0, 1}

        After num=5: dp |= dp << 5
                     a = dp = 3 (bin: 0000011)
                     b = dp << 5 = 96 (bin: 1100000)
                     c = a | b = 99 (bin: 1100011)
                     Sums: {0, 1, 5, 6}

        After num=11: dp |= dp << 11
                      a = dp = 99 (bin: 00000001100011)
                      b = dp << 11 = 202752 (bin: 110001100000000)
                      c = a | b = 202851 (bin: 110001101100011)
                      Sums: {0, 1, 5, 6, 11, 12, 16, 17}

        Check: (dp & (1 << 11)) != 0
               a = dp = 202851 (bin: 110001101100011)
               b = 1 << 11 = 2048 (bin: 100000000000)
               c = a & b = 2048 (bin: 100000000000)
               c != 0 → bit 11 is set → True!
        """
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = 1

        for num in nums:
            dp |= dp << num

            # Early termination: found target sum!
            if (dp & (1 << target)) != 0:
                return True

        return False
```

## Complexity

| Time        | Space  |
| ----------- | ------ |
| O(n \* sum) | O(sum) |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode), [AlgoMaster 75](/catalog/algo-master-75).