DSA problem
Partition Equal Subset Sum
Given a non-empty array nums containing only positive integers, find whether you can partition the array into two subsets such that the sum of elements in both subsets is equal.
This problem is a classic instance of the 0/1 knapsack family. The two subsets must collectively contain every element, so each must sum to exactly sum(nums) / 2. That immediately reveals two facts: if the total sum is odd no valid partition exists, and otherwise the problem reduces to asking whether a subset of nums can sum to target = sum / 2.
The classical 0/1 knapsack framing applies directly. Each number can be either placed in the chosen subset or left out — a binary decision per item. We do not care about the values of the unchosen elements, only whether the chosen ones can hit target. This turns the question into "does there exist a subset summing to target?", a yes/no reachability problem rather than an optimization.
The optimal solution uses a 1D boolean DP rolling array of length target + 1, where dp[s] represents whether sum s is achievable using some subset of the numbers seen so far. We initialize dp[0] = true (the empty subset achieves sum 0) and for each num we iterate s from target down to num so each item is used at most once. After processing every number, dp[target] answers the question. The full algorithm runs in O(n * target) time and O(target) space.
Examples
nums = [1,5,11,5]truenums = [1,2,3,5]falsenums = [2,2,3,5]falseConstraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
- The sum of all elements is bounded so that the DP table remains tractable.
- All values are positive integers.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.