Partition Equal Subset Sum LeetCode 416

LeetCode 416 — Partition Equal Subset Sum — gives you a non-empty array of positive integers nums. Return true if you can partition it into two subsets such that the sum of elements in both subsets is equal.

If the total sum is odd, partitioning into two equal halves is impossible — return false immediately. If the total is even, the problem reduces to: does a subset of nums sum to total/2? This is the classic subset sum problem, a special case of the 0/1 knapsack.

The 0/1 knapsack formulation uses a boolean DP array where dp[j] indicates whether a subset summing to j exists. Starting with dp[0] = true, iterate through each number and update the array right-to-left to avoid using the same element twice.

Compute total = sum(nums). If total is odd, return false. Set target = total / 2. Now the question is: can we select a subset of nums whose elements sum to exactly target? If yes, the remaining elements automatically sum to target as well.

This reduction is the key insight. It transforms a partition problem (which sounds like it requires examining all 2^n subsets) into a knapsack problem solvable in pseudo-polynomial time O(n * target).

The target is at most total/2, and total is at most 200 * 100 = 20,000 (given constraints: up to 200 elements, each up to 100). So target is at most 10,000, making the DP feasible with a 10,001-element boolean array.

Create a boolean array dp of size target + 1, initialized to false. Set dp[0] = true (the empty subset sums to 0). For each number num in nums, iterate j from target down to num. Set dp[j] = dp[j] OR dp[j - num].

The right-to-left iteration is critical. If we iterated left-to-right, dp[j - num] might already reflect the inclusion of the current num, allowing it to be used multiple times. Right-to-left ensures each element is used at most once — the defining constraint of 0/1 knapsack.

After processing all numbers, return dp[target]. If true, there exists a subset summing to target, and the partition is possible. The DP naturally handles all possible subset combinations without explicit enumeration.

Consider nums = [1, 5, 11, 5]. Total = 22, target = 11. dp = [T, F, F, F, F, F, F, F, F, F, F, F] (size 12). Process num=1: j=11 to 1, dp[1] = dp[1] OR dp[0] = T. dp = [T, T, F, F, F, F, F, F, F, F, F, F].

Process num=5: j=11 to 5. dp[6] = dp[6] OR dp[1] = T. dp[5] = dp[5] OR dp[0] = T. dp = [T, T, F, F, F, T, T, F, F, F, F, F]. Process num=11: j=11. dp[11] = dp[11] OR dp[0] = T. Found! Return true.

The subset {11} sums to 11, and {1, 5, 5} also sums to 11. We did not even need to process the last element. In practice, you can add an early return: if dp[target] becomes true during processing, return immediately.

In Python: 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]. Return dp[target].

In Java: boolean[] dp = new boolean[target + 1]. dp[0] = true. For each int num in nums: for (int j = target; j >= num; j--): dp[j] = dp[j] || dp[j - num]. Return dp[target]. Add early termination: if (dp[target]) return true inside the outer loop.

The bitset alternative in Python: bits = 1. For num in nums: bits |= bits << num. Return bool(bits & (1 << target)). This is often the fastest Python solution due to the efficiency of big-integer bit operations.

Time complexity is O(n * target) where n is the array length and target = sum/2. For each of n elements, we scan the dp array of size target+1. With the given constraints (n <= 200, target <= 10,000), this is at most 2,000,000 operations.

Space complexity is O(target) for the 1D dp array. The 2D formulation uses O(n * target) space but the 1D optimization (iterating right-to-left) compresses it to O(target). The bitset approach uses O(target / 8) bytes.

This is pseudo-polynomial — polynomial in the input size and the numeric values, but not polynomial in the number of bits needed to represent those values. For the given constraints, it is efficient. For very large sums, the problem becomes NP-hard.

Target Sum (LeetCode 494) is a direct extension: assign + or - to each number to reach a target. It reduces to subset sum with target = (sum + target) / 2. The DP formulation is nearly identical but counts the number of ways instead of checking existence.

Coin Change (LeetCode 322) is the unbounded knapsack variant where each coin can be used multiple times. The key difference: iterate left-to-right instead of right-to-left. Understanding when to use 0/1 vs unbounded knapsack is a critical interview skill.

Last Stone Weight II (LeetCode 1049) reduces to minimizing the difference between two subsets, which is equivalent to finding the largest subset sum <= total/2. It uses the same boolean DP as Partition Equal Subset Sum.