# 416. Partition Equal Subset Sum

[link](https://leetcode.com/problems/partition-equal-subset-sum/)
---

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.

#### Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

#### Example 2:

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

---

First, we calculate the total sum of all elements in the nums array. If the sum is not even (i.e., sum(nums) % 2 != 0), return False because it's not possible to partition the array into two subsets with equal sums.

Then we initialize a variable target to be half of the sum, i.e., target = sum(nums) // 2. This is the sum that each subset should achieve.

We create a set dp to keep track of the possible subset sums. Initialize it with a single value, 0, because initially, you can achieve a sum of 0 with an empty subset.

Iterate through the nums array in reverse order (from the last element to the first element) For each element nums[i], create a new set nextDp since we cannot operate the hashSet if we are iterating it. For each sum j in the dp set, do the following:

1. If j + nums[i] equals the target, return True because we've found a valid partition.

2. Add j + nums[i] and j to the nextDp set. The reason we add j is because we don't want to lose the values which are already in the dp.

3. Update the dp set to be the nextDp set.

After iterating through all elements in nums, if target is in the dp set, return True because you've found a valid partition; otherwise, return False.

#### Solution 1

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0:
            return False

        target = sum(nums) // 2
        dp = set()
        dp.add(0)
        for i in range(len(nums) - 1, -1, -1):
            nextDp = set()
            for j in dp:
                if (j + nums[i]) == target:
                    return True
                nextDp.add(j + nums[i])
                nextDp.add(j)

            dp = nextDp

        return True if target in dp else False
        

O(T): O(n(sum(nums)))
O(S): O(n)