Partition Equal Subset Sum LeetCode: Boolean 0/1 Knapsack

Partition Equal Subset Sum (#416) is one of the most important problems in the dynamic programming category on LeetCode. It asks a deceptively simple question: given an array of positive integers, can you partition it into two subsets with equal sum? Behind that question lies the classic 0/1 Knapsack pattern.

The key insight that unlocks this partition equal subset sum leetcode problem is a reduction. If the total sum of the array is S, then you need two subsets each summing to S/2. That means the entire problem reduces to: "is there a subset of the array that sums to exactly S/2?" This is the textbook subset sum problem, and it is solved with boolean DP.

In this walkthrough, we will break down the reduction, build the 1D DP solution step by step, explain why the backwards iteration matters, and trace through a concrete example so the pattern sticks.

You are given a non-empty array nums containing only positive integers. Return true if you can partition the array into two subsets such that the sum of elements in both subsets is equal. Otherwise, return false.

For example, given nums = [1,5,11,5], the total sum is 22. You can split it into [1,5,5] and [11], both summing to 11. The answer is true. For nums = [1,2,3,5], the total is 11 which is odd — you cannot split an odd total into two equal halves, so the answer is false.

The brute-force approach generates all possible subsets and checks if any of them sums to total/2. That is O(2^n) time — far too slow for the constraint of up to 200 elements. The subset sum dp approach brings this down to O(n * target) where target = total/2.

Once you recognize the reduction to subset sum, the DP formulation is straightforward. Define dp[j] as a boolean: can we form sum j using some subset of the elements we have processed so far? Initialize dp[0] = true (the empty subset sums to 0) and everything else to false.

For each number num in the array, update the DP array: dp[j] = dp[j] || dp[j - num] for every j from target down to num. The meaning is clear — sum j is achievable either if it was already achievable without this element, or if we can achieve j - num and then include this element to make j.

After processing all elements, dp[target] tells you whether a subset summing to target = total/2 exists. The time complexity is O(n * target) and the space complexity is O(target) with the 1D optimization. This is the classic subset sum boolean dp pattern.

This is one of the most commonly confused details in the 0-1 knapsack pattern. When updating the 1D DP array, you must iterate j from target down to num. If you iterate forward (from num to target), you risk using the same element multiple times in the same subset — that turns the 0/1 knapsack into an unbounded knapsack.

Here is why. If you process j in ascending order and dp[j - num] was just updated to true in this same pass (because of the current element), then dp[j] will also become true — effectively using num twice. Iterating backwards ensures that when you read dp[j - num], it still holds the value from the previous element pass.

This single detail is the difference between the 0/1 constraint (each element used at most once) and the unbounded variant (elements can be reused). Coin Change (#322) iterates forward because coins are unlimited. Partition Equal Subset Sum iterates backward because each number is used at most once.

Let us trace through nums = [1,5,11,5]. The total sum is 22, so target = 11. We initialize dp as a boolean array of size 12 (indices 0 through 11), with dp[0] = true and everything else false.

Process num = 1: iterate j from 11 down to 1. At j=1, dp[1] = dp[1] || dp[0] = false || true = true. All other j values remain false. After this pass: dp = [T,T,F,F,F,F,F,F,F,F,F,F].

Process num = 5: iterate j from 11 down to 5. At j=6, dp[6] = dp[6] || dp[1] = true. At j=5, dp[5] = dp[5] || dp[0] = true. After this pass: dp = [T,T,F,F,F,T,T,F,F,F,F,F].

Process num = 11: iterate j from 11 down to 11. At j=11, dp[11] = dp[11] || dp[0] = true. After this pass: dp[11] = true. We could stop here, but let us finish.

Process num = 5 (second 5): this would fill in a few more entries, but dp[11] is already true. The answer is true — we can partition [1,5,11,5] into two subsets with equal sum.

The most important edge case is an odd total sum. If the sum of all elements is odd, return false immediately — you cannot divide an odd number into two equal integers. This check should be the very first line of your solution before allocating the DP array.

A single-element array always returns false (you cannot split one element into two non-empty subsets with equal sum). An array where all elements are the same value, like [7,7,7,7], works if the count is even (total = 28, target = 14, achievable with two 7s).

Watch the constraint: nums.length can be up to 200 and each value up to 100, making the maximum total 20,000 and target 10,000. The DP array fits comfortably in memory, and O(200 * 10,000) = O(2,000,000) operations is well within time limits.

Partition Equal Subset Sum is the gateway problem for the 0/1 Knapsack pattern. Once you understand how to reduce partition to subset sum, and how the backwards-iterating 1D DP works, you have the foundation for a whole family of problems. The can partition equal pattern appears again and again in DP interviews.

From here, the natural next steps are Coin Change (#322) which uses the unbounded variant (forward iteration), and Target Sum (#494) which extends subset sum to count the number of ways rather than just checking feasibility. Each builds on exactly the same DP structure with small modifications.

The core takeaway is this: when you see a problem asking about partitioning, subsets, or achieving a target sum, think knapsack. Identify whether elements can be reused (unbounded) or not (0/1), set up the DP array, and choose your iteration direction accordingly. Review this pattern with YeetCode flashcards to make it second nature before your next interview.