0/1 Knapsack & Partition Equal Subset Sum.

In Simple Words: Target is totalSum / 2. If sum is odd, partition is impossible. Maintain a 1D Boolean DP Set of achievable subset sums: for each number, add n + existingSum into the set. Return target in dp.

• Time: $O(N \cdot \text{target})$ | Space: $O(\text{target})$

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0: return False
    target = total // 2
    dp = {0}
    for n in nums:
        dp |= {t + n for t in dp if t + n <= target}
    return target in dp