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] <= 100Problem 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.
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.
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.
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.
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 | 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 |
| 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 |
DP 15. Partition Equal Subset Sum | DP on Subsequences • take U forward • 355,493 views views
Watch 9 more video solutions →Practice Partition Equal Subset Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor