Partition Equal Subset Sum

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

The brute-force approach

Generate every subset, check if its sum equals totalSum/2.

total = sum(nums)
if total % 2 != 0: return False
target = total // 2
for mask in range(1 << n):
    if sum(nums[i] for i in range(n) if mask >> i & 1) == target:
        return True
return False

O(2^n) — trying all subsets.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

Why do you iterate the dp array from right to left (target down to num) when processing each number?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.