228. Partition Equal Subset Sum
🔗 LeetCode Problem: 416. Partition Equal Subset Sum
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, DP - Subsequences, 0/1 Knapsack
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 <= 200
- 1 <= nums[i] <= 100
🌳 Visual Understanding - Using nums = [1, 5, 11, 5]
The Problem We're Solving:
Given: nums = [1, 5, 11, 5]
Goal: Can we split into 2 subsets with equal sum?
Total sum = 1 + 5 + 11 + 5 = 22
For equal partition:
Each subset must have sum = 22/2 = 11
Question: Can we select numbers that sum to 11? 🤔
If YES → remaining numbers also sum to 11 ✓
If NO → impossible to partition equally ✗
Finding the Partition:
Array: [1, 5, 11, 5]
Target: 11 (half of total sum)
Try to make 11:
Option 1: [11]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Select: 11
Sum: 11 ✓
Remaining: [1, 5, 5] → sum = 11 ✓
Partition found!
Subset 1: [11]
Subset 2: [1, 5, 5]
Option 2: [1, 5, 5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Select: 1, 5, 5
Sum: 11 ✓
Remaining: [11] → sum = 11 ✓
Another valid partition!
Subset 1: [1, 5, 5]
Subset 2: [11]
Answer: true (partition exists) ✓
Example Where Partition is IMPOSSIBLE:
Array: [1, 2, 3, 5]
Total sum = 1 + 2 + 3 + 5 = 11
Is 11 even? NO (11 is odd)
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Can't split odd sum into two equal parts!
11/2 = 5.5 (not an integer)
Answer: false ✗
RULE: If total sum is ODD, partition is impossible! 🔑
Another Impossible Example:
Array: [1, 2, 5]
Total sum = 1 + 2 + 5 = 8 (even)
Target = 8/2 = 4
Try to make 4:
[1]: sum = 1 ✗
[2]: sum = 2 ✗
[5]: sum = 5 (too big!) ✗
[1, 2]: sum = 3 ✗
[1, 5]: sum = 6 (too big!) ✗
[2, 5]: sum = 7 (too big!) ✗
[1, 2, 5]: sum = 8 (too big!) ✗
No way to make exactly 4!
Answer: false ✗
Even sum doesn't guarantee partition exists!
Must actually find the subset! 🔑
🧠 The AHA Moment - Why This Problem Is Special
The KEY Transformation:
ORIGINAL PROBLEM:
"Partition array into 2 equal subsets"
Seems complex! Two subsets to track? 😰
TRANSFORMED PROBLEM:
"Can we find subset that sums to total/2?"
Much simpler! One subset to track! 😊
WHY THIS WORKS:
Total sum = S
Subset 1 sum = S/2
Subset 2 sum = S - S/2 = S/2 ✓
If we can make S/2, the remaining MUST also be S/2!
This transforms the problem into:
"Subset Sum Problem" - Classic 0/1 Knapsack! 🎯
The Key Insight - Subset Sum:
SUBSET SUM PROBLEM:
Given: array of numbers, target sum
Question: Can we select numbers (0/1 choice for each)
that sum exactly to target?
This is EXACTLY what we need!
For nums = [1, 5, 11, 5], target = 11:
Can we select some numbers that sum to 11?
For each number, we have 2 choices:
- Include it in subset (1)
- Don't include it (0)
This is 0/1 Knapsack pattern! 🔑
Building Intuition:
Think of it like packing a knapsack:
Knapsack capacity: 11
Items: [1, 5, 11, 5]
For each item:
Include? → Capacity left = 11 - item_value
Skip? → Capacity stays same
Can we fill EXACTLY 11?
Item 1 (value=1):
Include → need 10 more
Skip → need 11 more
Item 5 (value=5):
Include → need 6 more (if we had 11)
Skip → need 11 more
Item 11 (value=11):
Include → need 0 more (EXACT!) ✓
Skip → continue...
Found a way to make exactly 11!
🔴 Approach 1: Brute Force (Try All Subsets)
📐 Function Definition
Function Signature:
boolean canPartition(int[] nums)
What it represents:
Input Parameter nums:
- Array of positive integers
- Each element used exactly once (0/1 choice)
- Example: nums = [1, 5, 11, 5]
Return Value (boolean): - true if equal partition exists - false if impossible - Example: true
Purpose: - Calculate total sum - Check if sum is even (early exit if odd) - Try all possible subsets - For each number: include or skip - Check if any subset sums to target
Key Understanding:
For nums = [1, 5, 11, 5], target = 11:
At each index, two choices:
Include nums[i] → solve(i+1, target - nums[i])
Skip nums[i] → solve(i+1, target)
Try all combinations recursively!
💡 Intuition
The simplest idea: Try all possible subsets!
Think of it like choosing items:
Array: [1, 5, 11, 5]
Target: 11
Decision tree:
Start (target=11)
/ \
Include 1 Skip 1
(target=10) (target=11)
/ \ / \
Include 5 Skip 5 Include 5 Skip 5
(target=5) (target=10) (target=6) (target=11)
... ... ... ...
At each step:
- Include current number → reduce target
- Skip current number → keep same target
Try ALL paths! If any reaches target=0, we found it! ✓
📝 Implementation
class Solution {
public boolean canPartition(int[] nums) {
// Calculate total sum
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
// If sum is odd, can't partition equally
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
// Try all subsets starting from index 0
return helper(nums, 0, target);
}
private boolean helper(int[] nums, int index, int target) {
// Base case: target reached!
if (target == 0) return true;
// Base case: no more items or target negative
if (index >= nums.length || target < 0) {
return false;
}
// Choice 1: Include current number
if (helper(nums, index + 1, target - nums[index])) {
return true;
}
// Choice 2: Skip current number
if (helper(nums, index + 1, target)) {
return true;
}
return false;
}
}
🔍 Detailed Dry Run: nums = [1, 5, 11, 5], target = 11
totalSum = 22
target = 11
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE (Partial - showing successful path)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(nums, 0, 11)
│
├─ Include nums[0]=1: helper(nums, 1, 10)
│ ├─ Include nums[1]=5: helper(nums, 2, 5)
│ │ ├─ Include nums[2]=11: helper(nums, 3, -6)
│ │ │ return false (negative target)
│ │ │
│ │ └─ Skip nums[2]=11: helper(nums, 3, 5)
│ │ ├─ Include nums[3]=5: helper(nums, 4, 0)
│ │ │ return true ✓ (target=0!)
│ │ │
│ │ Found path: [1, 5, 5] sums to 11!
│ │ return true ✓
│ │
│ return true ✓
│
return true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SUCCESSFUL PATH FOUND:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Decisions made:
index 0 (1): Include → target becomes 10
index 1 (5): Include → target becomes 5
index 2 (11): Skip → target stays 5
index 3 (5): Include → target becomes 0 ✓
Selected subset: [1, 5, 5] = 11 ✓
Remaining subset: [11] = 11 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Note: There are many other paths in the tree
but we stop as soon as we find one successful path!
Why This Is Slow:
Decision tree has 2^n paths (each element: include or skip)
For each of n elements: 2 choices
Total combinations: 2^n
Example:
n = 4: 2^4 = 16 paths
n = 10: 2^10 = 1,024 paths
n = 20: 2^20 = 1,048,576 paths
n = 200: 2^200 = astronomical!
This is why brute force is TOO SLOW! ❌
BUT: Many paths explore same (index, target) states!
This is where memoization helps! 🔑
📊 Complexity Analysis
Time Complexity: O(2^n)
n = number of elements
At each element: 2 choices (include or skip)
Total paths: 2^n
For n = 200: completely impractical!
WAY TOO SLOW! ❌
Space Complexity: O(n)
Recursion stack depth
In worst case, depth = n
Why This Is Slow:
❌ Tries every possible subset
❌ Repeats same (index, target) states
❌ Exponential time complexity
✅ But correct and easy to understand!
We need to CACHE the results! → Memoization!
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
boolean canPartition(int[] nums)
What it represents:
Variables we track:
- memo[index][target] = Can we make target using nums[index..n-1]?
- If computed, reuse it!
- If not computed, compute and cache it!
Purpose: - Same recursive logic as brute force - But CACHE results to avoid recomputation - Each (index, target) state solved only ONCE!
Key Understanding:
Brute force calls helper(2, 5) many times
Memoization calls helper(2, 5) ONCE, caches result
Example:
First time helper(2, 5) called:
- Compute answer (true/false)
- Store in memo[2][5]
Next time helper(2, 5) called:
- Check memo[2][5]
- Found! Return immediately
- No recomputation! ✓
This saves MASSIVE amounts of work!
💡 Intuition
The smart idea: Remember what we've already checked!
Think of it like a checklist:
WITHOUT memoization (brute force):
Question: "Can we make 5 using items from index 2?"
You: *explore all possibilities*
Later, same question again!
You: *explore all possibilities AGAIN* ❌
WITH memoization:
Question: "Can we make 5 using items from index 2?"
You: *explore all possibilities*
You: *write in checklist: "[2, 5] = true"*
Later, same question again!
You: *check checklist*
You: "It's true!" ✓
You: *instant answer!*
The checklist is the memo array!
📝 Implementation
class Solution {
private Boolean[][] memo;
public boolean canPartition(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
memo = new Boolean[nums.length][target + 1];
return helper(nums, 0, target);
}
private boolean helper(int[] nums, int index, int target) {
// Base case: target reached!
if (target == 0) return true;
// Base case: no more items or target negative
if (index >= nums.length || target < 0) {
return false;
}
// Check memo (our checklist!)
if (memo[index][target] != null) {
return memo[index][target];
}
// Choice 1: Include current number
boolean include = helper(nums, index + 1, target - nums[index]);
// Choice 2: Skip current number
boolean skip = helper(nums, index + 1, target);
// Save to memo before returning!
memo[index][target] = include || skip;
return memo[index][target];
}
}
🔍 Detailed Dry Run: nums = [1, 5, 11, 5], target = 11
totalSum = 22
target = 11
memo = Boolean[4][12] (all null initially)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: helper(nums, 0, 11)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
index = 0, target = 11
memo[0][11] = null (not computed)
Try include nums[0]=1:
┌─ CALL: helper(nums, 1, 10)
│ index = 1, target = 10
│ memo[1][10] = null
│
│ Try include nums[1]=5:
│ ┌─ CALL: helper(nums, 2, 5)
│ │ index = 2, target = 5
│ │ memo[2][5] = null
│ │
│ │ Try include nums[2]=11:
│ │ ┌─ CALL: helper(nums, 3, -6)
│ │ │ target < 0
│ │ └─ return false
│ │
│ │ Try skip nums[2]=11:
│ │ ┌─ CALL: helper(nums, 3, 5)
│ │ │ index = 3, target = 5
│ │ │ memo[3][5] = null
│ │ │
│ │ │ Try include nums[3]=5:
│ │ │ ┌─ CALL: helper(nums, 4, 0)
│ │ │ │ target == 0
│ │ │ └─ return true ✓
│ │ │
│ │ │ include = true
│ │ │ memo[3][5] = true ✓
│ │ └─ return true ✓
│ │
│ │ skip = true
│ │ memo[2][5] = true ✓
│ └─ return true ✓
│
│ include = true
│ memo[1][10] = true ✓
└─ return true ✓
include = true
memo[0][11] = true ✓
return true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL memo state (only computed cells shown):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo[0][11] = true
memo[1][10] = true
memo[2][5] = true
memo[3][5] = true
Each state computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Found subset [1, 5, 5] that sums to 11!
Why This Works:
KEY INSIGHT:
Each unique (index, target) state is solved ONCE
Result is cached in memo[index][target]
Future calls return cached result instantly
Comparison:
Brute force: Same state explored multiple times
Memoization: Same state computed ONCE, cached
This transforms exponential → polynomial time!
📊 Complexity Analysis
Time Complexity: O(n × sum)
n = number of elements
sum = total sum of array
States: n × (sum/2) = n × sum/2
Each state computed ONCE
Work per state: O(1)
Total: O(n × sum)
For n = 200, sum = 20,000:
200 × 20,000 = 4,000,000 operations
MUCH better than 2^200! ✓
Space Complexity: O(n × sum)
Memo array: O(n × sum)
Recursion stack: O(n)
Total: O(n × sum)
🟢 Approach 3: Bottom-Up DP (Iterative)
📐 Function Definition
Function Signature:
boolean canPartition(int[] nums)
What it represents:
DP Array:
- dp[i][j] = Can we make sum j using first i elements?
- Build from dp[0][0], dp[0][1], ..., up to dp[n][target]
- Each value uses previous values!
Purpose: - Compute answers for all (i, j) states in order - For each element, for each possible sum - Use previously computed dp values!
Key Understanding:
Bottom-up builds from smallest to largest:
dp[0][0] = true (base: 0 elements make sum 0)
dp[0][j] = false (can't make any sum with 0 elements)
dp[i][j]: Can we make sum j using first i elements?
Option 1: Don't use nums[i-1] → dp[i-1][j]
Option 2: Use nums[i-1] → dp[i-1][j - nums[i-1]]
Build up the table incrementally!
💡 Intuition
The systematic idea: Build table from bottom up!
Think of it like filling a grid:
Sums: 0 1 2 3 4 5 ... 11
Items:
0 T F F F F F ... F
1 (1) T T F F F F ... F
2 (5) T T F F F T ... F
3 (11) T T F F F T ... T
4 (5) T T F F F T ... T
Start with no items (row 0)
Add items one by one (rows 1, 2, 3, 4)
Each cell uses cells from previous row!
Build from bottom-left to top-right!
📝 Implementation
class Solution {
public boolean canPartition(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
int n = nums.length;
// dp[i][j] = can make sum j using first i elements
boolean[][] dp = new boolean[n + 1][target + 1];
// Base case: can always make sum 0 (empty subset)
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
// Build table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
// Option 1: Don't include nums[i-1]
dp[i][j] = dp[i - 1][j];
// Option 2: Include nums[i-1] (if possible)
if (j >= nums[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][target];
}
}
🔍 Detailed Dry Run: nums = [1, 5, 11, 5], target = 11
totalSum = 22
target = 11
n = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZE DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Base case: dp[i][0] = true for all i
j: 0 1 2 3 4 5 6 7 8 9 10 11
i=0 (none) T F F F F F F F F F F F
i=1 (1) T F F F F F F F F F F F
i=2 (5) T F F F F F F F F F F F
i=3 (11) T F F F F F F F F F F F
i=4 (5) T F F F F F F F F F F F
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD TABLE ROW BY ROW
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Row i=1: nums[0] = 1
━━━━━━━━━━━━━━━━━━━━
For j=1:
Don't use 1: dp[0][1] = F
Use 1: dp[0][1-1] = dp[0][0] = T ✓
dp[1][1] = T
For j=2 to 11:
Don't use 1: dp[0][j] = F
Use 1: dp[0][j-1] = F
dp[1][j] = F
j: 0 1 2 3 4 5 6 7 8 9 10 11
i=1 (1) T T F F F F F F F F F F
Row i=2: nums[1] = 5
━━━━━━━━━━━━━━━━━━━━
For j=1 to 4:
Can't use 5 (j < 5)
dp[2][j] = dp[1][j]
For j=5:
Don't use 5: dp[1][5] = F
Use 5: dp[1][5-5] = dp[1][0] = T ✓
dp[2][5] = T
For j=6:
Don't use 5: dp[1][6] = F
Use 5: dp[1][6-5] = dp[1][1] = T ✓
dp[2][6] = T
For j=7 to 11:
Don't use 5: dp[1][j] = F
Use 5: dp[1][j-5] = F
dp[2][j] = F
j: 0 1 2 3 4 5 6 7 8 9 10 11
i=2 (5) T T F F F T T F F F F F
Row i=3: nums[2] = 11
━━━━━━━━━━━━━━━━━━━━
For j=1 to 10:
Can't use 11 (j < 11)
dp[3][j] = dp[2][j]
For j=11:
Don't use 11: dp[2][11] = F
Use 11: dp[2][11-11] = dp[2][0] = T ✓
dp[3][11] = T
j: 0 1 2 3 4 5 6 7 8 9 10 11
i=3 (11) T T F F F T T F F F F T
Row i=4: nums[3] = 5
━━━━━━━━━━━━━━━━━━━━
For j=1 to 4:
Can't use 5
dp[4][j] = dp[3][j]
For j=5:
Don't use 5: dp[3][5] = T
dp[4][5] = T ✓
For j=6:
Don't use 5: dp[3][6] = T
dp[4][6] = T ✓
For j=7 to 10:
Don't use 5: dp[3][j] = F
Use 5: dp[3][j-5] = ?
j=7: dp[3][2] = F
j=8: dp[3][3] = F
j=9: dp[3][4] = F
j=10: dp[3][5] = T ✓
dp[4][10] = T
For j=11:
Don't use 5: dp[3][11] = T
dp[4][11] = T ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP TABLE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
j: 0 1 2 3 4 5 6 7 8 9 10 11
i=0 T F F F F F F F F F F F
i=1 (1) T T F F F F F F F F F F
i=2 (5) T T F F F T T F F F F F
i=3 (11) T T F F F T T F F F F T
i=4 (5) T T F F F T T F F F T T
Answer: dp[4][11] = true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INTERPRETATION:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[4][11] = true means:
"Using first 4 elements [1,5,11,5],
we CAN make sum 11"
Possible subsets that sum to 11:
[11] ✓
[1, 5, 5] ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works - Visual Understanding:
Each cell dp[i][j] answers:
"Can we make sum j using first i items?"
To compute dp[i][j], we look at:
1. Previous row, same column: dp[i-1][j]
(don't use current item)
2. Previous row, j-nums[i-1] columns back: dp[i-1][j-nums[i-1]]
(use current item)
If EITHER is true, dp[i][j] = true!
Build table row by row, each using previous row!
Classic 0/1 Knapsack pattern! 🎯
📊 Complexity Analysis
Time Complexity: O(n × sum)
n = number of elements
sum = total sum of array
Outer loop: n iterations
Inner loop: sum/2 iterations
Total: n × (sum/2) = O(n × sum)
For n = 200, sum = 20,000:
200 × 20,000 = 4,000,000 operations
Very manageable! ✓
Space Complexity: O(n × sum)
DP table of size (n+1) × (sum/2+1)
Total: O(n × sum)
🟣 Approach 4: Space-Optimized DP (1D Array)
💡 Intuition
The clever observation: We only need previous row!
Notice in 2D DP:
dp[i][j] only depends on dp[i-1][j] and dp[i-1][j-nums[i-1]]
We only look at PREVIOUS ROW!
We don't need the entire table!
Optimization:
Instead of 2D array: dp[n][target]
Use 1D array: dp[target]
Process right to left to avoid overwriting!
📝 Implementation
class Solution {
public boolean canPartition(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
// dp[j] = can we make sum j?
boolean[] dp = new boolean[target + 1];
dp[0] = true; // Base case
// Process each number
for (int num : nums) {
// Traverse right to left to avoid overwriting!
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
}
🔍 Detailed Dry Run: nums = [1, 5, 11, 5], target = 11
target = 11
dp = [T, F, F, F, F, F, F, F, F, F, F, F]
0 1 2 3 4 5 6 7 8 9 10 11
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS EACH NUMBER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process num = 1:
━━━━━━━━━━━━━━━━━━━━
For j=11 to 1 (right to left):
j=11: dp[11] = dp[11] || dp[10] = F || F = F
j=10: dp[10] = dp[10] || dp[9] = F || F = F
...
j=2: dp[2] = dp[2] || dp[1] = F || F = F
j=1: dp[1] = dp[1] || dp[0] = F || T = T ✓
dp = [T, T, F, F, F, F, F, F, F, F, F, F]
Process num = 5:
━━━━━━━━━━━━━━━━━━━━
For j=11 to 5 (right to left):
j=11: dp[11] = dp[11] || dp[6] = F || F = F
j=10: dp[10] = dp[10] || dp[5] = F || F = F
...
j=6: dp[6] = dp[6] || dp[1] = F || T = T ✓
j=5: dp[5] = dp[5] || dp[0] = F || T = T ✓
dp = [T, T, F, F, F, T, T, F, F, F, F, F]
Process num = 11:
━━━━━━━━━━━━━━━━━━━━
For j=11:
j=11: dp[11] = dp[11] || dp[0] = F || T = T ✓
dp = [T, T, F, F, F, T, T, F, F, F, F, T]
Process num = 5:
━━━━━━━━━━━━━━━━━━━━
For j=11 to 5 (right to left):
j=11: dp[11] = dp[11] || dp[6] = T || T = T
j=10: dp[10] = dp[10] || dp[5] = F || T = T ✓
j=9: dp[9] = dp[9] || dp[4] = F || F = F
j=8: dp[8] = dp[8] || dp[3] = F || F = F
j=7: dp[7] = dp[7] || dp[2] = F || F = F
j=6: dp[6] = dp[6] || dp[1] = T || T = T
j=5: dp[5] = dp[5] || dp[0] = T || T = T
dp = [T, T, F, F, F, T, T, F, F, F, T, T]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP ARRAY:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp = [T, T, F, F, F, T, T, F, F, F, T, T]
0 1 2 3 4 5 6 7 8 9 10 11
Answer: dp[11] = true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why Right-to-Left Matters:
CRITICAL: Process j from target down to num!
Why?
If we go left to right:
dp[j-num] gets updated first
Then dp[j] uses the NEW dp[j-num]
This means using same item TWICE! ❌
If we go right to left:
dp[j] uses OLD dp[j-num]
This means using item at most ONCE! ✓
Example:
num = 5
LEFT TO RIGHT (WRONG):
j=5: dp[5] = dp[5] || dp[0] = T (correct)
j=10: dp[10] = dp[10] || dp[5] = T ❌
(using the NEW dp[5], means using 5 twice!)
RIGHT TO LEFT (CORRECT):
j=10: dp[10] = dp[10] || dp[5] = F (old dp[5])
j=5: dp[5] = dp[5] || dp[0] = T ✓
Right to left preserves 0/1 property! 🔑
📊 Complexity Analysis
Time Complexity: O(n × sum)
Same as 2D approach
But with better space!
Space Complexity: O(sum)
Only 1D array of size target + 1
MUCH better than O(n × sum)!
Optimal space! ✓
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ PARTITION EQUAL SUBSET SUM - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Brute Force │ O(2^n) │ O(n) │ High │ Start │
│ Memoization │ O(n×sum) │ O(n×sum) │ Good │ Good │
│ 2D DP │ O(n×sum) │ O(n×sum) │ Best │ Best │
│ 1D DP │ O(n×sum) │ O(sum) │ Optimal ✓ │ Optimal ✓│
└──────────────┴───────────┴───────────┴────────────┴──────────┘
For interviews: Show 2D DP first, then optimize to 1D!
💻 Complete Working Code
class Solution {
public boolean canPartition(int[] nums) {
return dp1D(nums);
}
// Approach 4: Space-Optimized 1D DP - O(n×sum) time, O(sum) space
private boolean dp1D(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
// Approach 3: 2D DP - O(n×sum) time, O(n×sum) space
private boolean dp2D(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
int n = nums.length;
boolean[][] dp = new boolean[n + 1][target + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][target];
}
// Approach 2: Memoization - O(n×sum) time, O(n×sum) space
private Boolean[][] memo;
private boolean memoization(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
memo = new Boolean[nums.length][target + 1];
return helperMemo(nums, 0, target);
}
private boolean helperMemo(int[] nums, int index, int target) {
if (target == 0) return true;
if (index >= nums.length || target < 0) return false;
if (memo[index][target] != null) return memo[index][target];
boolean include = helperMemo(nums, index + 1, target - nums[index]);
boolean skip = helperMemo(nums, index + 1, target);
memo[index][target] = include || skip;
return memo[index][target];
}
// Approach 1: Brute Force - O(2^n) time
private boolean bruteForce(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % 2 != 0) return false;
return helperBrute(nums, 0, totalSum / 2);
}
private boolean helperBrute(int[] nums, int index, int target) {
if (target == 0) return true;
if (index >= nums.length || target < 0) return false;
return helperBrute(nums, index + 1, target - nums[index])
|| helperBrute(nums, index + 1, target);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.canPartition(new int[] { 1, 5, 11, 5 }) == true);
System.out.println(s.canPartition(new int[] { 1, 2, 3, 5 }) == false);
}
}
🔑 Key Insights
The KEY Transformation:
ORIGINAL: "Partition into 2 equal subsets"
→ Seems complex!
TRANSFORMED: "Find subset that sums to total/2"
→ Much simpler!
Why? If one subset sums to total/2,
the other MUST also sum to total/2!
This is the insight that makes the problem solvable! 🔑
Early Termination:
RULE 1: If total sum is ODD → impossible!
Can't split odd number into two equal parts
Example: 11/2 = 5.5 (not integer)
Return false immediately! ✓
RULE 2: If total sum is EVEN → maybe possible
But still need to check if subset exists
Example: [1, 2, 5] → sum=8, target=4
But can't make 4 → still false!
Pattern Recognition:
This is CLASSIC 0/1 KNAPSACK!
0/1 Knapsack:
- Items with weights and values
- Each item used 0 or 1 times
- Maximize value within weight limit
This Problem:
- Numbers are "items"
- Each number used 0 or 1 times
- Check if we can make exact sum
SAME PATTERN - Subset Sum variant! 🎯
Space Optimization:
2D DP: O(n × sum) space
1D DP: O(sum) space
How? Only need previous row!
Key: Process right to left to avoid overwriting!
This is the classic DP space optimization! ✓
🎪 Memory Aid
"Transform: partition → subset sum!"
"Odd sum → impossible immediately!"
"0/1 choice for each number!"
"Right to left to preserve 0/1 property!" ✨
⚠️ Common Mistakes
- ❌ Not checking if sum is odd (easy early exit!)
- ❌ Forgetting base case dp[0] = true
- ❌ Processing left to right in 1D DP (uses item twice!)
- ❌ Confusing with unbounded knapsack (each item once only!)
- ❌ Off-by-one errors (array indices vs DP indices)
✅ Interview Talking Points
"This problem transforms into Subset Sum - a classic 0/1 Knapsack variant.
Key insight:
To partition array into two equal subsets,
we just need to find ONE subset that sums to total/2.
If we can make total/2, the remaining MUST also be total/2!
Early optimization:
If total sum is odd → impossible immediately!
Can't split odd number into two equal integers.
DP Approach:
dp[i][j] = can we make sum j using first i elements?
Base case: dp[i][0] = true (empty subset)
For each element, two choices:
Include: dp[i-1][j - nums[i-1]]
Skip: dp[i-1][j]
If either is true → dp[i][j] = true
Space optimization:
Only need previous row → use 1D array
Process right to left to avoid using item twice
Complexity: O(n×sum) time, O(sum) space
This is optimal for this problem!"
📝 Quick Revision Notes
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum % 2 != 0) {
return false;
}
// return recursive(nums, 0, sum / 2);
// Boolean[][] memo = new Boolean[nums.length][1 + (sum / 2)];
// return topDown(nums, 0, sum / 2, memo);
return bottomUp(nums, sum / 2);
}
private boolean bottomUp(int[] nums, int k) {
int len = nums.length;
// dp[i][j] => Using first i numbers, can we make sum j?
boolean[][] dp = new boolean[1 + len][1 + k];
// base case - zero sum
// Making sum 0 is always possible - take no elements
for (int i = 0; i <= len; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) {
dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i][j];
}
}
}
return dp[len][k];
}
private boolean topDown(int[] nums, int index, int k, Boolean[][] memo) {
if (k == 0) {
return true;
}
if (k < 0 || index == nums.length) {
return false;
}
if (memo[index][k] != null) {
return memo[index][k];
}
boolean take = topDown(nums, index + 1, k - nums[index], memo);
boolean no_take = topDown(nums, index + 1, k, memo);
if (take || no_take) {
return memo[index][k] = true;
}
return memo[index][k] = false;
}
private boolean recursive(int[] nums, int index, int k) {
// step 3: base case 1
if (k == 0) {
return true;
}
// step 3: base case 2
if (k < 0 || index == nums.length) {
return false;
}
// step 1
// This is not earlier unbound knapsack.
// This is kind of classic take - no take as you need to find
// subset and cannot take multiple copies of the same number.
// consider the current number and proceed
boolean take = recursive(nums, index + 1, k - nums[index]);
// do not consider the current number and proceed
boolean no_take = recursive(nums, index + 1, k);
if (take || no_take) {
return true;
}
// step 2
return false;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.canPartition(new int[] { 1, 5, 11, 5 }) == true);
System.out.println(s.canPartition(new int[] { 1, 2, 3, 5 }) == false);
System.out.println(s.canPartition(new int[] { 1, 2, 3, 5 }) == false);
System.out.println(s.canPartition(new int[] { 1, 2, 5 }) == false);
System.out.println(s.canPartition(new int[] { 20, 1, 16, 2, 17, 16, 8, 15, 7 }) == true);
}
}
🎉 Congratulations!
You've mastered Partition Equal Subset Sum - classic 0/1 Knapsack!
What You Learned:
✅ Problem transformation - Partition → Subset Sum
✅ Early termination - Odd sum check
✅ 0/1 Knapsack - Each element used once
✅ Brute force - Try all subsets
✅ Memoization - Cache (index, target) states
✅ 2D DP - Bottom-up table building
✅ 1D DP - Space optimization (right to left!)
This is THE canonical 0/1 Knapsack problem! 🚀✨