Partition Equal Subset Sum - Solution & Explanation
Problem Statement
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.
Example 1:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
Approach Overview
Problem Overview: Given an integer array nums, determine whether it can be split into two subsets whose sums are equal. The problem reduces to checking if a subset exists whose sum equals half of the total array sum.
Approach 1: Recursive with Memoization (Top-Down DP) (Time: O(n * target), Space: O(n * target))
Start by computing the total sum of the array. If the sum is odd, equal partition is impossible. Otherwise the goal becomes finding a subset that adds up to target = total / 2. Use recursion to decide for each index whether to include the current number or skip it. Without optimization this creates an exponential search tree, but memoization caches results for (index, remaining_sum) so the same state is never recomputed. A hash map or 2D memo table stores whether a state leads to a valid subset. This turns the brute-force search into a manageable top‑down dynamic programming solution.
The recursive state transitions are straightforward: either subtract the current value from the remaining target or move to the next index unchanged. If any path reaches exactly zero, a valid subset exists. This pattern appears frequently in dynamic programming problems that originate from subset or knapsack decisions.
Approach 2: Dynamic Programming (Subset Sum DP) (Time: O(n * target), Space: O(target))
This approach converts the subset search into a bottom‑up DP problem. Instead of recursion, maintain a boolean DP array where dp[s] indicates whether a subset with sum s is achievable. Initialize dp[0] = true because a sum of zero is always possible using an empty subset. Then iterate through each number in the array and update the DP table in reverse order so each number is used at most once.
For every value num, update states from target down to num. If dp[s - num] was previously reachable, mark dp[s] as reachable. This effectively simulates choosing or skipping each number without storing full subset combinations. The reverse iteration is critical; it prevents the same element from being reused multiple times.
The algorithm finishes once all numbers are processed. If dp[target] is true, a subset exists whose sum equals half of the total, meaning the array can be partitioned into two equal subsets. This is the classic subset‑sum formulation used across many dynamic programming interview problems.
Recommended for interviews: Interviewers typically expect the bottom‑up subset sum DP with the 1D boolean array. It demonstrates that you recognized the reduction to a knapsack-style problem and optimized space from O(n * target) to O(target). Explaining the recursive memoization version first shows clear reasoning about the decision tree, while implementing the optimized DP solution shows strong problem‑solving and performance awareness.
Approach 1: Dynamic Programming Approach
This problem can be viewed as a variation of the subset sum problem. The idea is to determine if there is a subset of the given array whose sum is exactly half of the total sum. We use dynamic programming to store information about the previous computations, specifically a DP array where dp[i] indicates whether it's possible to achieve sum i using the elements of the array.
The code starts by calculating the total sum of the array. If this sum is odd, it's impossible to split it into two equal subsets, so it returns false. Otherwise, it computes the target sum as half of the total sum and initializes a DP array dp of size target + 1. The DP array keeps track of which sums can be formed with the numbers encountered so far. It iterates through each number, updating the DP array to indicate whether a subset including that number can achieve each possible sum. Finally, it checks if the target sum is achievable.
Complexity
Time Complexity: O(N * target), where N is the number of elements in nums and target is half of the total sum.
Space Complexity: O(target), due to the DP array.
Approach 2: Recursive with Memoization Approach
This approach uses recursion along with memoization to solve the problem. We try to find a subset that totals half of the overall sum. As we attempt different combinations, we keep track of subproblem solutions we have already computed, which optimizes our solution by avoiding redundant computations.
The solution checks if the total sum is odd. If it is, partitioning cannot be done equally, so the function returns false. Otherwise, it calls a recursive function that tries to partition the array recursively, considering both including and excluding each number. The function is optimized by storing already computed results for specific states (a combination of current index and remaining target) in a map, thus enabling efficient backtracking without redundant calculations.
Complexity
Time Complexity: O(N * target), where N is the number of elements in nums and target is half of the total sum. The memoization ensures each unique call is computed only once.
Space Complexity: O(N * target) due to the recursive stack and memoization map.
Approach 3: Dynamic Programming
First, we calculate the total sum s of the array. If the total sum is odd, it cannot be divided into two subsets with equal sums, so we directly return false. If the total sum is even, we set the target subset sum to m = \frac{s}{2}. The problem is then transformed into: does there exist a subset whose element sum is m?
We define f[i][j] to represent whether it is possible to select several numbers from the first i numbers so that their sum is exactly j. Initially, f[0][0] = true and the rest f[i][j] = false. The answer is f[n][m].
Considering f[i][j], if we select the i-th number x, then f[i][j] = f[i - 1][j - x]. If we do not select the i-th number x, then f[i][j] = f[i - 1][j]. Therefore, the state transition equation is:
$
f[i][j] = f[i - 1][j] or f[i - 1][j - x] if j geq x
The final answer is f[n][m].
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n$ are half of the total sum of the array and the length of the array, respectively.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: Dynamic Programming (Space Optimization)
We notice that in Solution 1, f[i][j] is only related to f[i - 1][cdot]. Therefore, we can compress the two-dimensional array into a one-dimensional array.
The time complexity is O(n times m), and the space complexity is O(m). Where n is the length of the array, and m is half of the total sum of the array.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(N * target), where N is the number of elements in |
| Recursive with Memoization Approach | Time Complexity: O(N * target), where N is the number of elements in |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * target) | O(n * target) | Good for explaining the decision tree and converting brute force into top-down dynamic programming |
| Bottom-Up Dynamic Programming (1D Subset Sum) | O(n * target) | O(target) | Preferred interview solution when optimizing memory for subset-sum problems |
Video Solution
DP 15. Partition Equal Subset Sum | DP on Subsequences • take U forward • 384,340 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Partition Equal Subset Sum easy or hard?
How to solve Partition Equal Subset Sum in O(n)?
What is the best approach for Partition Equal Subset Sum?
What data structure is used in Partition Equal Subset Sum?
What is the time complexity of Partition Equal Subset Sum?
Partition Equal Subset Sum Python or Java solution approach?
Is Partition Equal Subset Sum asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Partition Equal Subset Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor