Partition Equal Subset Sum
Problem
Given a list of positive integers nums, return True if the array can be partitioned into two subsets such that the sums of the subsets are equal, and False otherwise.
- 1 ≤ nums.length ≤ 200
- 1 ≤ nums[i] ≤ 100
Example
nums = [1, 5, 11, 5]TrueThe total sum is 22, which is even. The problem reduces to finding a subset that sums to 11. One valid subset is [11], and the other subset is [1, 5, 5], both summing to 11. The algorithm first checks if the total sum is even; if not, it returns False immediately. Then it uses recursion with memoization to explore whether a subset with sum equal to half the total exists. The recursion explores including or excluding each number, caching results to avoid redundant computations.
Approach
Straightforward Solution
A brute-force approach tries all subsets, which is exponential in time (O(2^n)) and infeasible for larger inputs.
Core Observation
The problem reduces to determining if there exists a subset of nums whose sum equals half of the total sum. This is because if such a subset exists, the rest of the elements form the other subset with the same sum.
Path to Optimal
Recognizing the problem as a subset sum problem, dynamic programming can be applied. The key insight is to use recursion with memoization to avoid recomputing states. The state is defined by the current index and the current sum accumulated. By caching results for each (index, current_sum) pair, the algorithm avoids exponential recomputation and achieves polynomial time complexity.
Optimal Approach
Use a top-down recursive DP with memoization. The recursion tries two choices at each index: include the current number in the subset or exclude it. If at any point the current sum equals the target (half the total sum), return True. If the current sum exceeds the target or the index goes beyond the array, return False. Memoize results to prune redundant paths. This approach guarantees correctness and efficiency.
Time
O(n * target)
The recursion explores states defined by index and current_sum. There are at most n indices and target sums, so the total states are O(n * target). Each state is computed once due to memoization.
Space
O(n * target)
The memo dictionary stores results for each (index, current_sum) state, requiring O(n * target) auxiliary space. The recursion stack depth is O(n), which is dominated by the memo size.
Pattern Spotlight
Dynamic Programming (Top-Down Memoized Subset Sum)
When searching for a subset with a target sum, model the problem as a state space of (index, current_sum) and use memoization to prune repeated computations, transforming exponential brute force into polynomial time.
Solution
| 1 | class Solution:
|
| 2 | def canPartition(self, nums: list[int]) -> bool:
|
| 3 | total_sum = sum(nums)
|
| 4 | if total_sum % 2 != 0:
|
| 5 | return False
|
| 6 |
|
| 7 | target = total_sum // 2
|
| 8 | memo = {}
|
| 9 |
|
| 10 | def dp(i, current_sum):
|
| 11 | if current_sum == target:
|
| 12 | return True
|
| 13 | if i >= len(nums) or current_sum > target:
|
| 14 | return False
|
| 15 | if (i, current_sum) in memo:
|
| 16 | return memo[(i, current_sum)]
|
| 17 |
|
| 18 | res = (dp(i + 1, current_sum + nums[i]) or
|
| 19 | dp(i + 1, current_sum))
|
| 20 |
|
| 21 | memo[(i, current_sum)] = res
|
| 22 | return res
|
| 23 |
|
| 24 | return dp(0, 0) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public boolean canPartition(int[] nums) { |
| 6 | int total_sum = 0; |
| 7 | for (int num : nums) { |
| 8 | total_sum += num; |
| 9 | } |
| 10 | if (total_sum % 2 != 0) { |
| 11 | return false; |
| 12 | } |
| 13 | int target = total_sum / 2; |
| 14 | Map<String, Boolean> memo = new HashMap<>(); |
| 15 | |
| 16 | return dp(0, 0, nums, target, memo); |
| 17 | } |
| 18 | |
| 19 | private boolean dp(int i, int current_sum, int[] nums, int target, Map<String, Boolean> memo) { |
| 20 | if (current_sum == target) { |
| 21 | return true; |
| 22 | } |
| 23 | if (i >= nums.length || current_sum > target) { |
| 24 | return false; |
| 25 | } |
| 26 | String key = i + "," + current_sum; |
| 27 | if (memo.containsKey(key)) { |
| 28 | return memo.get(key); |
| 29 | } |
| 30 | |
| 31 | boolean res = dp(i + 1, current_sum + nums[i], nums, target, memo) || |
| 32 | dp(i + 1, current_sum, nums, target, memo); |
| 33 | memo.put(key, res); |
| 34 | return res; |
| 35 | } |
| 36 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <string> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | bool canPartition(vector<int>& nums) { |
| 10 | int total_sum = 0; |
| 11 | for (int num : nums) { |
| 12 | total_sum += num; |
| 13 | } |
| 14 | if (total_sum % 2 != 0) { |
| 15 | return false; |
| 16 | } |
| 17 | int target = total_sum / 2; |
| 18 | unordered_map<string, bool> memo; |
| 19 | return dp(0, 0, nums, target, memo); |
| 20 | } |
| 21 | |
| 22 | private: |
| 23 | bool dp(int i, int current_sum, const vector<int>& nums, int target, unordered_map<string, bool>& memo) { |
| 24 | if (current_sum == target) { |
| 25 | return true; |
| 26 | } |
| 27 | if (i >= (int)nums.size() || current_sum > target) { |
| 28 | return false; |
| 29 | } |
| 30 | string key = to_string(i) + "," + to_string(current_sum); |
| 31 | auto it = memo.find(key); |
| 32 | if (it != memo.end()) { |
| 33 | return it->second; |
| 34 | } |
| 35 | |
| 36 | bool res = dp(i + 1, current_sum + nums[i], nums, target, memo) || |
| 37 | dp(i + 1, current_sum, nums, target, memo); |
| 38 | memo[key] = res; |
| 39 | return res; |
| 40 | } |
| 41 | }; |
| 1 | var canPartition = function(nums) { |
| 2 | const total_sum = nums.reduce((a, b) => a + b, 0); |
| 3 | if (total_sum % 2 !== 0) { |
| 4 | return false; |
| 5 | } |
| 6 | const target = total_sum / 2; |
| 7 | const memo = new Map(); |
| 8 | |
| 9 | function dp(i, current_sum) { |
| 10 | if (current_sum === target) { |
| 11 | return true; |
| 12 | } |
| 13 | if (i >= nums.length || current_sum > target) { |
| 14 | return false; |
| 15 | } |
| 16 | const key = i + ',' + current_sum; |
| 17 | if (memo.has(key)) { |
| 18 | return memo.get(key); |
| 19 | } |
| 20 | |
| 21 | const res = dp(i + 1, current_sum + nums[i]) || dp(i + 1, current_sum); |
| 22 | memo.set(key, res); |
| 23 | return res; |
| 24 | } |
| 25 | |
| 26 | return dp(0, 0); |
| 27 | }; |
Step-by-Step Solution
Check Total Sum Parity and Initialize Memoization
| 3 | total_sum = sum(nums)
|
| 4 | if total_sum % 2 != 0:
|
| 5 | return False
|
| 7 | target = total_sum // 2
|
| 8 | memo = {}
|
Objective
To quickly determine if partitioning is impossible due to odd total sum and prepare memoization storage for DP.
Key Insight
If the total sum is odd, it's impossible to split the array into two equal subsets, so the function returns False immediately. This early exit avoids unnecessary computation. Initializing a memo dictionary prepares for caching recursive results, which is essential for pruning redundant computations in the DP recursion.
Interview Quick-Check
Core Logic
Checking total sum parity is a constant-time filter that prevents futile recursion when partitioning is impossible.
Common Pitfalls & Bugs
Forgetting to check sum parity leads to wasted computation and incorrect results on odd sums.
State & Boundaries
Memoization dictionary keys are tuples of (index, current_sum), representing unique recursion states.
Recursively Explore Subsets with Memoized DP
| 10 | def dp(i, current_sum):
|
| 11 | if current_sum == target:
|
| 12 | return True
|
| 13 | if i >= len(nums) or current_sum > target:
|
| 14 | return False
|
| 15 | if (i, current_sum) in memo:
|
| 16 | return memo[(i, current_sum)]
|
| 18 | res = (dp(i + 1, current_sum + nums[i]) or
|
| 19 | dp(i + 1, current_sum))
|
| 21 | memo[(i, current_sum)] = res
|
| 22 | return res
|
Objective
To determine if a subset summing to target exists by recursively including or excluding each number, while caching results to avoid recomputation.
Key Insight
The recursion models the subset sum problem as a decision at each index: include the current number or skip it. The base cases handle success (current_sum equals target) and failure (index out of bounds or sum exceeded). Memoization stores results for each (index, current_sum) state, pruning repeated exploration of identical subproblems. This transforms an exponential search into a polynomial-time DP solution.
Interview Quick-Check
Core Logic
The recursion tries both including and excluding the current number, returning True if either leads to a valid subset sum.
State & Boundaries
Base cases ensure recursion stops when the target sum is reached or when the search space is exhausted.
Common Pitfalls & Bugs
Failing to memoize leads to exponential time due to repeated state exploration.
Complexity
Memoization reduces the time complexity from O(2^n) to O(n * target) by caching results.
Return Final Result from Recursive DP
| 24 | return dp(0, 0) |
Objective
To initiate the recursive search from the first index with zero accumulated sum and return whether a valid partition exists.
Key Insight
Starting the recursion at index 0 and current_sum 0 explores all subsets systematically. The final return value reflects whether any subset sums to the target, which directly answers the partition problem. This call triggers the entire memoized DP process.
Interview Quick-Check
Core Logic
The initial call sets the recursion in motion, exploring all subset combinations from the start.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if current_sum == target:Return True if current_sum equals target.
Reaching the target sum means a valid subset has been found, so the recursion can terminate successfully.
if (i, current_sum) in memo:Recursively explore including or excluding the current number.
This line embodies the core decision: either add nums[i] to the current subset or skip it, exploring all subset combinations.
if total_sum % 2 != 0:Check if the total sum is odd.
If the total sum is odd, the array cannot be split into two equal subsets, so the function returns False immediately, avoiding unnecessary computation.
return TrueReturn False if index is out of bounds or current_sum exceeds target.
These base cases prune invalid paths: exceeding the target or exhausting the array without success means no valid subset exists along this path.
if i >= len(nums) or current_sum > target:Check if the current state (index, current_sum) is memoized.
Memoization lookup prevents redundant computation by returning cached results for previously solved states.
return FalseReturn False when total sum is odd.
This early return prevents futile recursive exploration when partitioning is impossible due to sum parity.
memo = {}Initialize a memoization dictionary to cache recursion results.
Memoization is essential to avoid recomputing the same (index, current_sum) states, transforming exponential recursion into polynomial time.
return FalseReturn the cached result if found in memo.
Returning cached results prunes the recursion tree, ensuring each state is computed once, which is critical for efficiency.
return memo[(i, current_sum)]Store the result of the recursive exploration in memo.
Caching the result for the current state ensures future calls with the same parameters return instantly, preventing exponential blowup.
dp(i + 1, current_sum))Recursive call to include the current number in the subset.
Including the current number advances the search towards the target sum by increasing current_sum.
memo[(i, current_sum)] = resRecursive call to exclude the current number from the subset.
Excluding the current number explores alternative subsets that might reach the target without it.
return resMemoize the combined result of including or excluding the current number.
Storing the OR of both recursive paths captures whether any valid subset exists from this state.
total_sum = sum(nums)Calculate the total sum of all numbers in the input list.
The total sum determines if partitioning into two equal subsets is possible; an odd sum immediately disqualifies the input.
target = total_sum // 2Calculate the target sum as half of the total sum.
The problem reduces to finding a subset that sums exactly to this target, enabling the partition.
def dp(i, current_sum):Define the recursive function dp with parameters index and current_sum.
This function explores whether a subset starting at index can reach the target sum by accumulating current_sum, forming the core of the top-down DP approach.
res = (dp(i + 1, current_sum + nums[i]) orReturn the computed result for the current state.
This returns the answer up the recursion stack, enabling the final determination of partition feasibility.
return dp(0, 0)Start the recursion from index 0 and current sum 0.
This initiates the DP exploration of all subsets, returning whether a valid partition exists.
Test Your Understanding
Why is it necessary to memoize the results of subproblems defined by (index, current_sum) in this recursive solution?
Because without memoization, the recursion would recompute the same states multiple times, leading to exponential time complexity. Memoization ensures each unique state is computed once, pruning redundant exploration and enabling polynomial time.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Partition Equal Subset Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Partition Equal Subset Sum drill