Partition Equal Subset Sum

main.md

Question

Approach

I first calculated the total sum of the array. If the sum is odd, it's impossible to split it equally, so I returned False. Otherwise, I set the target as total_sum // 2. I then used a DP set to track all reachable subset sums. For each number in the array, I updated the set with new possible sums by adding it to existing ones. If the target is reached, I returned True. If not, I returned False.

Implementation

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

        target = total // 2
        possible = set([0])

        for num in nums:
            new_possible = set()
            for t in possible:
                if t + num == target:
                    return True
                if t + num < target:
                    new_possible.add(t + num)
            possible.update(new_possible)

        return target in possible

Complexities

• Time: O(n * target)
• Space: O(n)