233. Last Stone Weight II
🔗 LeetCode Problem: 1049. Last Stone Weight II
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, DP - Subsequences, Partition Problem
Problem Statement
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Example 2:
Input: stones = [31,26,33,21,40]
Output: 5
Constraints:
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
🔍 Let's Discover the Pattern Together
Start with Small Examples
Let's not jump to the solution. Let's understand what's really happening by trying small examples:
Example 1: stones = [2, 7]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Smash 2 and 7 → 7 - 2 = 5
Result: 5
Example 2: stones = [2, 7, 4]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Let's try different smashing orders:
Order A: (2, 7) first → 5, then (5, 4) → 1
Order B: (2, 4) first → 2, then (7, 2) → 5
Order C: (7, 4) first → 3, then (3, 2) → 1
Different orders → different results!
Best result: 1
Example 3: stones = [5, 5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Smash 5 and 5 → 0
Result: 0
Observation: Equal stones cancel out!
Notice the Pattern
Let's look closer at Example 2:
stones = [2, 7, 4]
Order A: (7 - 2) - 4 = 5 - 4 = 1
Order C: (7 - 4) - 2 = 3 - 2 = 1
Both simplify to: 7 - 2 - 4 = 1
🎯 KEY OBSERVATION: The ORDER doesn't matter!
What matters is which stones get ADDED vs SUBTRACTED!
Think of it like this:
+7 - 2 - 4 = 1 ✓
-2 + 7 - 4 = 1 ✓
We're essentially assigning + or - signs to each stone!
The Breakthrough
If we assign signs:
Group with +: {7, 4} → sum = 11
Group with -: {2} → sum = 2
Result: |11 - 2| = 9 ✗
Another assignment:
Group with +: {7} → sum = 7
Group with -: {2, 4} → sum = 6
Result: |7 - 6| = 1 ✓
AHA! The problem is really:
"Partition stones into 2 groups"
"Minimize |sum(group1) - sum(group2)|"
💡 The AHA Moment - Connecting to Known Patterns
Does This Remind You of Something?
Think about Problem 228: Partition Equal Subset Sum
That problem asked:
"Can we partition into TWO EQUAL groups?"
This problem asks:
"Partition into two groups with MINIMUM difference"
Connection:
- Both involve partitioning into 2 groups
- Both care about sums
- Equal partition is just special case (difference = 0)
- Both use 0/1 Knapsack approach!
The Mathematical Insight
Let's derive why this works:
Given:
- S1 = sum of group 1
- S2 = sum of group 2
- S1 + S2 = total
Want: Minimize |S1 - S2|
Since S2 = total - S1:
|S1 - S2| = |S1 - (total - S1)|
= |2×S1 - total|
To minimize this, S1 should be as close to total/2 as possible!
Transform:
Original: "Minimize difference when partitioning"
Becomes: "Find subset with sum closest to total/2"
This is 0/1 KNAPSACK - the subset sum pattern!
🔴 Approach 1: Brute Force (Try All Partitions)
📐 Function Definition
Function Signature:
int helper(int index, int sum1, int total)
What does this function compute?
- Input index: Current stone we're deciding on
- Input sum1: Sum of group 1 so far
- Input total: Total sum of all stones
- Output: Minimum difference achievable from index onwards
What does the recursive call represent?
- For each stone at index, we have 2 choices:
- Add to group1 → helper(index+1, sum1 + stone, total)
- Add to group2 → helper(index+1, sum1, total) (don't add to sum1)
- Return minimum of both choices
The Recursive Structure:
For each stone at index:
Choice 1: Add to group1 → helper(index+1, sum1 + stone, total)
Choice 2: Add to group2 → helper(index+1, sum1, total)
Return: Minimum of both choices
Base case:
All stones assigned → return |sum1 - (total - sum1)|
Why this works:
Every partition assigns each stone to one of 2 groups.
With n stones, there are 2^n possible partitions.
We try all of them and find the minimum difference.
💡 Intuition
Think of it as assigning +/- signs:
stones = [2, 7, 4]
All possibilities:
(+2, +7, +4) → sum1=13, sum2=0 → diff=13
(+2, +7, -4) → sum1=9, sum2=4 → diff=5
(+2, -7, +4) → sum1=6, sum2=7 → diff=1 ✓
(+2, -7, -4) → sum1=2, sum2=11 → diff=9
(-2, +7, +4) → sum1=11, sum2=2 → diff=9
(-2, +7, -4) → sum1=7, sum2=6 → diff=1 ✓
(-2, -7, +4) → sum1=4, sum2=9 → diff=5
(-2, -7, -4) → sum1=0, sum2=13 → diff=13
Try all 2^n combinations, find minimum!
📝 Implementation
class Solution {
public int lastStoneWeightII(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
return helper(stones, 0, 0, total);
}
private int helper(int[] stones, int index, int sum1, int total) {
// Base case: all stones assigned
if (index == stones.length) {
int sum2 = total - sum1;
return Math.abs(sum1 - sum2);
}
// Choice 1: Add current stone to group1
int include = helper(stones, index + 1, sum1 + stones[index], total);
// Choice 2: Add current stone to group2
int exclude = helper(stones, index + 1, sum1, total);
return Math.min(include, exclude);
}
}
🔍 Detailed Dry Run: stones = [2, 7, 4]
total = 13
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(0, 0, 13)
/ \
+2 to g1 +2 to g2
helper(1, 2, 13) helper(1, 0, 13)
/ \ / \
+7 to g1 +7 to g2 +7 to g1 +7 to g2
h(2,9,13) h(2,2,13) h(2,7,13) h(2,0,13)
/ \ / \ / \ / \
+4 -4 +4 -4 +4 -4 +4 -4
Each leaf computes difference:
Path 1: sum1=13, sum2=0, diff=13
Path 2: sum1=9, sum2=4, diff=5
Path 3: sum1=6, sum2=7, diff=1 ✓
Path 4: sum1=2, sum2=11, diff=9
Path 5: sum1=11, sum2=2, diff=9
Path 6: sum1=7, sum2=6, diff=1 ✓
Path 7: sum1=4, sum2=9, diff=5
Path 8: sum1=0, sum2=13, diff=13
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Trace path 3 in detail:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(0, 0, 13)
include: helper(1, 2, 13) ← add stone 2 to group1
include: helper(2, 9, 13) ← add stone 7 to group1
exclude: helper(3, 9, 13) ← add stone 4 to group2
Base: |9 - 4| = 5
Result: 5
exclude: helper(2, 2, 13) ← add stone 7 to group2
include: helper(3, 6, 13) ← add stone 4 to group1
Base: |6 - 7| = 1 ✓
Result: 1
Result: min(5, 1) = 1
Return: 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 1 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Optimal partitions:
{2,4} vs {7} → |6-7| = 1
{7} vs {2,4} → |7-6| = 1
Why This Is Slow
Time Complexity: O(2^n)
- 2 choices per stone
- n stones
- Total: 2^n combinations
For stones = [2,7,4,1,8,1]:
2^6 = 64 combinations to try
Many overlapping subproblems:
- helper(1, 2, 13) might be called multiple times
- Same (index, sum1) state computed repeatedly
Need memoization! →
📊 Complexity Analysis
Time Complexity: O(2^n)
n = number of stones
Try all 2^n partitions
Exponential - too slow!
Space Complexity: O(n)
Recursion stack depth
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
int helper(int index, int sum1, int total)
What it represents:
Variables we track:
- memo[index][sum1] = Minimum difference when processing stones[index...] with current sum1
- If computed, reuse it!
- If not computed (-1), compute and cache it!
Purpose: - Same recursive logic as brute force - But CACHE results for (index, sum1) states - Each unique state solved only ONCE!
Key Understanding:
Without memo:
helper(1, 2, 13) called multiple times
Each time: explore all possibilities ✗
With memo:
helper(1, 2, 13) called first time → compute, cache
Called again → return cached result immediately ✓
This transforms O(2^n) → O(n × sum)!
💡 Intuition
Think of it as a lookup table:
State: (index=1, sum1=2)
Question: "What's min diff from here?"
First time:
Compute by trying all paths
Result: 1
Store in memo[1][2] = 1
Second time same state appears:
Check memo[1][2]
Found! Return 1 immediately
No recomputation!
The memo saves massive amounts of work!
📝 Implementation
class Solution {
private int[][] memo;
public int lastStoneWeightII(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
// memo[index][sum1] = min diff from this state
// sum1 can be 0 to total
memo = new int[stones.length][total + 1];
for (int i = 0; i < stones.length; i++) {
for (int j = 0; j <= total; j++) {
memo[i][j] = -1; // -1 means not computed
}
}
return helper(stones, 0, 0, total);
}
private int helper(int[] stones, int index, int sum1, int total) {
// Base case
if (index == stones.length) {
int sum2 = total - sum1;
return Math.abs(sum1 - sum2);
}
// Check memo
if (memo[index][sum1] != -1) {
return memo[index][sum1];
}
// Try both choices
int include = helper(stones, index + 1, sum1 + stones[index], total);
int exclude = helper(stones, index + 1, sum1, total);
int result = Math.min(include, exclude);
// Cache result
memo[index][sum1] = result;
return result;
}
}
🔍 Detailed Dry Run: stones = [2, 7, 4]
total = 13
memo = int[3][14] (all -1 initially)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPUTATION WITH MEMOIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: helper(0, 0, 13)
memo[0][0] = -1 (not computed)
include: helper(1, 2, 13)
memo[1][2] = -1 (not computed)
include: helper(2, 9, 13)
memo[2][9] = -1 (not computed)
include: helper(3, 13, 13)
Base: |13 - 0| = 13
return 13
exclude: helper(3, 9, 13)
Base: |9 - 4| = 5
return 5
result = min(13, 5) = 5
memo[2][9] = 5 ✓
return 5
exclude: helper(2, 2, 13)
memo[2][2] = -1 (not computed)
include: helper(3, 6, 13)
Base: |6 - 7| = 1 ✓
return 1
exclude: helper(3, 2, 13)
Base: |2 - 11| = 9
return 9
result = min(1, 9) = 1
memo[2][2] = 1 ✓
return 1
result = min(5, 1) = 1
memo[1][2] = 1 ✓
return 1
exclude: helper(1, 0, 13)
memo[1][0] = -1 (not computed)
include: helper(2, 7, 13)
memo[2][7] = -1 (not computed)
include: helper(3, 11, 13)
Base: |11 - 2| = 9
return 9
exclude: helper(3, 7, 13)
Base: |7 - 6| = 1 ✓
return 1
result = min(9, 1) = 1
memo[2][7] = 1 ✓
return 1
exclude: helper(2, 0, 13)
memo[2][0] = -1 (not computed)
include: helper(3, 4, 13)
Base: |4 - 9| = 5
return 5
exclude: helper(3, 0, 13)
Base: |0 - 13| = 13
return 13
result = min(5, 13) = 5
memo[2][0] = 5 ✓
return 5
result = min(1, 5) = 1
memo[1][0] = 1 ✓
return 1
result = min(1, 1) = 1
memo[0][0] = 1 ✓
return 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL MEMO STATE (selected entries):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo[0][0] = 1
memo[1][0] = 1
memo[1][2] = 1
memo[2][0] = 5
memo[2][2] = 1
memo[2][7] = 1
memo[2][9] = 5
Each state computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 1 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works
KEY INSIGHT:
Same (index, sum1) state appears multiple times in brute force tree
With memo: compute once, reuse many times
Example:
State (2, 2) might appear in multiple branches
Brute force: recompute each time
Memoization: compute once, cache, reuse
Transforms exponential → polynomial!
📊 Complexity Analysis
Time Complexity: O(n × sum)
n = number of stones
sum = total sum of all stones
Unique states: n × sum
Each state computed once
Total: O(n × sum)
For stones = [2,7,4,1,8,1]:
n = 6, sum = 23
6 × 23 = 138 states
Much better than 2^6 = 64 (but with overlaps)!
Space Complexity: O(n × sum)
Memo array: O(n × sum)
Recursion stack: O(n)
Total: O(n × sum)
🎯 The Critical Transformation - Why Boolean DP?
The Problem with Integer DP
Our memoization stores:
memo[index][sum1] = minimum difference
But here's the issue:
At each state, we're computing MIN across many paths
The DP table is huge: n × total
And we're doing unnecessary work!
Why?
We don't actually need the MINIMUM at each state
We only need it at the END (when index = n)
The Key Realization
Question: What do we REALLY need to know?
Answer: Which sums are ACHIEVABLE!
If we know all achievable sums for group1,
we can compute all possible differences at the end:
For each achievable sum1:
sum2 = total - sum1
diff = |sum1 - sum2|
Find minimum difference!
This changes our DP from:
"What's the minimum difference?" (integer DP)
To:
"Can we make this sum?" (boolean DP)
The Mathematical Insight
We want sum1 close to total/2
If sum1 > total/2:
Then sum2 < total/2
This is the same as checking sum2 close to total/2
(Just swap the groups!)
So we ONLY need to check:
sum1 from 0 to total/2
This reduces our search space by HALF!
New goal:
Find the LARGEST achievable sum ≤ total/2
Then: answer = total - 2×max_sum
Why This Formula Works
If max_sum = largest achievable sum ≤ total/2
Then:
sum1 = max_sum
sum2 = total - max_sum
difference = |sum1 - sum2|
= |max_sum - (total - max_sum)|
= |2×max_sum - total|
Since max_sum ≤ total/2:
2×max_sum ≤ total
So: 2×max_sum - total ≤ 0
Therefore:
|2×max_sum - total| = total - 2×max_sum
That's our formula! ✓
🟢 Approach 3: Bottom-Up DP - Boolean Subset Sum
📐 The Transformation Explained
From Integer DP to Boolean DP:
Old DP (memoization):
memo[index][sum1] = minimum difference using stones[index...]
Type: Integer
Goal: Find minimum across all states
New DP (boolean):
dp[i][j] = can we make sum j using first i stones?
Type: Boolean
Goal: Find largest j ≤ total/2 where dp[n][j] = true
Then compute: total - 2×j
Why this works better:
Instead of tracking minimum difference at each state,
we just track: "Is this sum achievable?"
At the end, we scan all achievable sums,
pick the one closest to total/2,
compute difference once!
This is MUCH simpler and cleaner! ✓
💡 Intuition - Mapping From Memoization
Memoization asked: "What's min diff from (index, sum1)?"
Boolean DP asks: "Can we make sum j using first i stones?"
The transition:
Memoization (Integer DP):
memo[i][j] = min(
helper(i+1, j + stones[i]), // include
helper(i+1, j) // exclude
)
Boolean DP:
dp[i][j] = dp[i-1][j] // don't use stone i-1
OR dp[i-1][j - stones[i-1]] // use stone i-1
Same pick/no-pick logic!
Just changed from MIN to OR (achievable or not)!
🧒 DERIVING BASE CASES - Step by Step (ELI5)
Step 1: What Does dp[i][j] Mean?
Imagine you have toy blocks (stones).
dp[i][j] answers ONE simple question:
"Can I stack exactly weight j using the first i blocks?"
It's just YES or NO (true or false)!
Examples:
stones = [2, 7, 4]
dp[0][0] = "Can I make weight 0 using 0 blocks?"
→ YES! Don't use any blocks = weight 0 ✓
dp[0][5] = "Can I make weight 5 using 0 blocks?"
→ NO! I have no blocks! ✗
dp[1][2] = "Can I make weight 2 using first 1 block (stone=2)?"
→ YES! Use the stone of weight 2 ✓
dp[1][7] = "Can I make weight 7 using first 1 block (stone=2)?"
→ NO! I only have a stone of weight 2, can't make 7 ✗
dp[2][9] = "Can I make weight 9 using first 2 blocks (2, 7)?"
→ YES! Use both: 2+7=9 ✓
Simple: true/false for "can I make this weight?"
Step 2: Deriving Base Cases FROM RECURSIVE
RECURSIVE BASE CASE (from brute force/memoization):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
When index = n (no stones left to process):
Can we make sum 0? → YES (don't use anything)
Can we make sum > 0? → NO (no stones available!)
This is our stopping condition in recursion!
BOTTOM-UP TRANSLATION:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
In bottom-up, "no stones left" means "using 0 stones"
In our table, this is ROW 0 (i=0)
So:
dp[0][0] = true ← Can make sum 0 with 0 stones? YES!
dp[0][1] = false ← Can make sum 1 with 0 stones? NO!
dp[0][2] = false ← Can make sum 2 with 0 stones? NO!
...
dp[0][target] = false
Think of it visually:
"I have ZERO blocks. Can I build height 0?" → YES
"I have ZERO blocks. Can I build height 5?" → NO
That's why: dp[0][0] = true, all other dp[0][j] = false!
This is DIRECTLY from recursive base case! ✓
Step 3: WHY i Starts from 1? (ELI5)
WHY: for (int i = 1; i <= n; i++)
^^^ starts from 1, not 0!
Let's understand step by step:
ROW 0 (i=0): This is our BASE CASE!
dp[0][0] = true (already filled!)
dp[0][others] = false (already filled!)
This row means: "using 0 stones, what can we make?"
Answer: Only sum 0!
WE DON'T BUILD THIS ROW - IT'S GIVEN!
ROW 1 (i=1): Now we consider the FIRST stone!
stones[0] = 2 (remember: array index 0 = first stone)
Question: "using first 1 stone (which is weight 2), what can we make?"
We BUILD this row using information from ROW 0!
For each sum j:
Can we make j WITHOUT using stone 2? → Check dp[0][j]
Can we make j BY using stone 2? → Check dp[0][j-2]
ROW 2 (i=2): Now we consider FIRST TWO stones!
stones[0]=2, stones[1]=7
Question: "using first 2 stones, what can we make?"
We BUILD this row using information from ROW 1!
And so on...
SUMMARY:
Row 0 = BASE CASE (pre-filled, no computation needed)
Rows 1,2,3,... = BUILD using previous row
That's why loop: for (int i = 1; i <= n; i++)
^^^^^^^ start BUILDING from row 1
Step 4: WHY j Starts from 0? (CRITICAL!)
WHY: for (int j = 0; j <= target; j++)
^^^ starts from 0, not 1!
This is SUPER IMPORTANT! Let me show you what breaks if we skip j=0:
WRONG (starting from j=1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) { // ❌ SKIP j=0!
dp[i][j] = dp[i-1][j];
if (j >= stones[i-1]) {
dp[i][j] = dp[i][j] || dp[i-1][j - stones[i-1]];
}
}
}
What's wrong?
dp[1][0] never gets set! It stays false!
dp[2][0] never gets set! It stays false!
dp[3][0] never gets set! It stays false!
...
But we NEED dp[i][0] = true for ALL i!
Why do we need it?
"Can we make sum 0 using any number of stones?"
→ YES! Just don't use any of them!
This is important for the recurrence:
Example: If j = 2 and current stone = 2:
dp[i][2] = dp[i-1][2] || dp[i-1][2-2]
= dp[i-1][2] || dp[i-1][0]
^^^^^^^^^^
We NEED this to be true!
If dp[i-1][0] is false, we can't use the stone properly!
RIGHT (starting from j=0):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) { // ✓ Include j=0!
dp[i][j] = dp[i-1][j];
if (j >= stones[i-1]) {
dp[i][j] = dp[i][j] || dp[i-1][j - stones[i-1]];
}
}
}
Now what happens when j=0?
dp[i][0] = dp[i-1][0] (which is true from base case!)
if (0 >= stones[i-1]) → false, skip second part
Result: dp[i][0] = true ✓
This PROPAGATES "sum 0 is always possible" to all rows!
SIMPLE RULE TO REMEMBER:
If your base case sets dp[0][0] = true,
your j loop MUST start from 0!
Otherwise you lose that information! ✗
Step 5: The Recurrence - Where It Comes From
RECURSIVE LOGIC (from brute force):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(index, sum1):
For current stone at index:
Option 1: Don't use it → helper(index+1, sum1)
Option 2: Use it → helper(index+1, sum1 + stones[index])
Return MIN of both options
BOOLEAN DP TRANSLATION:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"Can we make sum j using first i stones?"
Option 1: Don't use stone i-1
→ Can we make sum j using first (i-1) stones?
→ dp[i-1][j]
Option 2: Use stone i-1
→ If we use stone i-1 (weight = stones[i-1])
→ We need remaining sum = j - stones[i-1]
→ Can we make (j - stones[i-1]) using first (i-1) stones?
→ dp[i-1][j - stones[i-1]]
EITHER option works (it's OR, not MIN):
dp[i][j] = dp[i-1][j] OR dp[i-1][j - stones[i-1]]
EXACTLY mirrors recursive pick/no-pick! ✓
Visual:
Integer DP: min(don't use, use)
Boolean DP: (don't use) OR (use)
Same structure, different operation!
Step 6: Complete Implementation with EVERY Detail Explained
public int lastStoneWeightII(int[] stones) {
// Step 1: Calculate total sum
int total = 0;
for (int stone : stones) {
total += stone;
}
// Step 2: Target is half of total
// We only need to check sums up to total/2
int target = total / 2;
int n = stones.length;
// Step 3: Create DP table
// dp[i][j] = can we make sum j using first i stones?
// Rows: 0 to n (using 0, 1, 2, ..., n stones)
// Cols: 0 to target (sums from 0 to target)
boolean[][] dp = new boolean[n + 1][target + 1];
// Step 4: BASE CASE - The Foundation!
// This comes DIRECTLY from recursive base case
// ROW 0: using 0 stones
dp[0][0] = true; // Can make sum 0 with 0 stones? YES!
// dp[0][1..target] = false (default boolean value)
// Can make sum 1,2,3,... with 0 stones? NO!
// This matches recursive: "no stones, sum 0" → possible
// "no stones, sum>0" → impossible
// Step 5: Fill DP table ROW by ROW
// Each row i represents: "using first i stones"
// WHY start from i=1? Because i=0 is base case (already filled)!
for (int i = 1; i <= n; i++) {
// For EACH possible sum from 0 to target
// WHY start from j=0? To propagate dp[i][0] = true!
// If we skip j=0, we lose "sum 0 always possible"!
for (int j = 0; j <= target; j++) {
// Option 1: DON'T use stone i-1 (array index i-1)
// Can we make sum j WITHOUT using current stone?
// YES if we could make it with previous i-1 stones
dp[i][j] = dp[i-1][j];
// Option 2: USE stone i-1
// Only possible if j >= stones[i-1]
// (can't use a stone heavier than our target sum!)
if (j >= stones[i-1]) {
// If we use stone i-1:
// Current stone contributes stones[i-1] weight
// We need (j - stones[i-1]) from previous stones
// Check: dp[i-1][j - stones[i-1]]
//
// Either option works → OR them
dp[i][j] = dp[i][j] || dp[i-1][j - stones[i-1]];
}
// At this point:
// dp[i][j] = true if we can make sum j using first i stones
// dp[i][j] = false otherwise
}
}
// Step 6: Find largest achievable sum ≤ target
// Scan from target down to 0
// First true value is our maxSum!
int maxSum = 0;
for (int j = target; j >= 0; j--) {
if (dp[n][j]) { // using all n stones
maxSum = j;
break; // found it!
}
}
// Step 7: Calculate final answer
// Formula: total - 2×maxSum
// This gives us minimum difference
return total - 2 * maxSum;
}
Step 7: COMPLETE Dry Run - See Every Cell
stones = [2, 7, 4]
total = 13
target = 6
n = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIAL STATE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
j: 0 1 2 3 4 5 6
i=0: T F F F F F F ← BASE CASE
i=1: ? ? ? ? ? ? ?
i=2: ? ? ? ? ? ? ?
i=3: ? ? ? ? ? ? ?
BASE CASE EXPLANATION:
dp[0][0] = true ← "0 stones, sum 0" → YES!
All others false ← "0 stones, sum>0" → NO!
This is DIRECTLY from recursive base case! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD ROW 1: i=1, Using stone stones[0]=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: "What sums can we make using first 1 stone (weight 2)?"
j=0: Can we make sum 0?
Don't use stone 2: dp[0][0] = T ✓
Use stone 2: 0 >= 2? NO, skip
Result: dp[1][0] = T
Meaning: Yes, make sum 0 by not using stone!
j=1: Can we make sum 1?
Don't use stone 2: dp[0][1] = F
Use stone 2: 1 >= 2? NO, skip
Result: dp[1][1] = F
Meaning: No, can't make sum 1 with stone of weight 2
j=2: Can we make sum 2?
Don't use stone 2: dp[0][2] = F
Use stone 2: 2 >= 2? YES!
Need: dp[0][2-2] = dp[0][0] = T ✓
Result: dp[1][2] = F OR T = T ✓
Meaning: Yes! Use stone 2 to make sum 2!
j=3: Can we make sum 3?
Don't use: dp[0][3] = F
Use: 3 >= 2? YES!
Need: dp[0][3-2] = dp[0][1] = F
Result: dp[1][3] = F OR F = F
Meaning: No, even with stone 2 can't make 3
j=4: Similar, Result: F
j=5: Similar, Result: F
j=6: Similar, Result: F
j: 0 1 2 3 4 5 6
i=0: T F F F F F F
i=1: T F T F F F F ← Can make {0, 2}
i=2: ? ? ? ? ? ? ?
i=3: ? ? ? ? ? ? ?
MEANING: With 1 stone (weight 2), achievable sums: {0, 2}
0: don't use stone
2: use stone
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD ROW 2: i=2, Adding stone stones[1]=7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: "What sums can we make using first 2 stones (2, 7)?"
j=0: dp[2][0] = dp[1][0] = T
j=1: dp[2][1] = dp[1][1] = F
j=2: dp[2][2] = dp[1][2] = T
j=3,4,5,6: Stone 7 is BIGGER than target (6)!
Can't use it for any sum ≤ 6
Just copy from row 1:
dp[2][3] = dp[1][3] = F
dp[2][4] = dp[1][4] = F
dp[2][5] = dp[1][5] = F
dp[2][6] = dp[1][6] = F
j: 0 1 2 3 4 5 6
i=0: T F F F F F F
i=1: T F T F F F F
i=2: T F T F F F F ← Same! Stone 7 too heavy
i=3: ? ? ? ? ? ? ?
MEANING: Stone 7 doesn't help (too heavy for target=6)
So row 2 = row 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD ROW 3: i=3, Adding stone stones[2]=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: "What sums can we make using all 3 stones (2, 7, 4)?"
j=0: dp[3][0] = dp[2][0] = T
j=1: Can we make sum 1?
Don't use 4: dp[2][1] = F
Use 4: 1 >= 4? NO
Result: dp[3][1] = F
j=2: Can we make sum 2?
Don't use 4: dp[2][2] = T ✓
Use 4: 2 >= 4? NO
Result: dp[3][2] = T
j=3: Can we make sum 3?
Don't use 4: dp[2][3] = F
Use 4: 3 >= 4? NO
Result: dp[3][3] = F
j=4: Can we make sum 4?
Don't use 4: dp[2][4] = F
Use 4: 4 >= 4? YES!
Need: dp[2][4-4] = dp[2][0] = T ✓
Result: dp[3][4] = F OR T = T ✓
Meaning: Yes! Use stone 4 alone!
j=5: Can we make sum 5?
Don't use 4: dp[2][5] = F
Use 4: 5 >= 4? YES!
Need: dp[2][5-4] = dp[2][1] = F
Result: dp[3][5] = F OR F = F
Meaning: No, would need sum 1 from previous stones
j=6: Can we make sum 6?
Don't use 4: dp[2][6] = F
Use 4: 6 >= 4? YES!
Need: dp[2][6-4] = dp[2][2] = T ✓
Result: dp[3][6] = F OR T = T ✓
Meaning: Yes! Use stone 4 + (stones making 2) = 4+2 = 6!
j: 0 1 2 3 4 5 6
i=0: T F F F F F F
i=1: T F T F F F F
i=2: T F T F F F F
i=3: T F T F T F T ← Final!
MEANING: With all stones {2,7,4}, achievable sums ≤ 6: {0, 2, 4, 6}
0: use nothing
2: use {2}
4: use {4}
6: use {2,4} ← This is our maxSum!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FIND LARGEST ACHIEVABLE SUM
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Scan from j=6 down to 0:
dp[3][6] = T → maxSum = 6 ✓ FOUND!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALCULATE FINAL ANSWER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
total = 13
maxSum = 6
answer = total - 2×maxSum
= 13 - 2×6
= 13 - 12
= 1 ✓
Interpretation:
Group1: sum = 6 (stones {2, 4})
Group2: sum = 7 (stone {7})
Difference = |6 - 7| = 1 ✓
This matches our brute force and memoization! ✓
Step 8: Key Insights Summary
1. WHY dp[0][0] = true?
→ From recursive: "no stones, sum 0" → possible!
→ Base case in bottom-up
2. WHY start i from 1?
→ Row 0 is base case (pre-filled)
→ We BUILD rows 1,2,3,... from it
3. WHY start j from 0?
→ MUST propagate dp[i][0] = true to all rows
→ Required for recurrence when j - stone = 0
→ Skipping j=0 breaks everything!
4. WHY this recurrence?
→ Exact mirror of recursive pick/no-pick
→ dp[i-1][j] = don't use stone
→ dp[i-1][j-stone] = use stone
→ OR them (boolean, not MIN)
5. WHY boolean instead of integer?
→ Don't need MIN at each state
→ Just need achievable sums
→ Compute difference at the end
→ Simpler and cleaner!
📊 Complexity Analysis
Time Complexity: O(n × target) = O(n × sum)
Two nested loops:
Outer: n iterations
Inner: target iterations
Total: O(n × target)
For stones=[2,7,4,1,8,1]:
n = 6, target = 11
6 × 11 = 66 operations ✓
Space Complexity: O(n × target)
DP table of size (n+1) × (target+1)
🔧 Approach 4: Space Optimization - 1D DP
The Observation
Notice in our 2D DP:
dp[i][j] only depends on dp[i-1][...]
We don't need ALL previous rows!
Just need the PREVIOUS ROW!
Idea: Use 1D array, update in place!
📝 Implementation
public int lastStoneWeightII(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
int target = total / 2;
// dp[j] = can we make sum j?
boolean[] dp = new boolean[target + 1];
dp[0] = true; // Base case
// Process each stone
for (int stone : stones) {
// CRITICAL: Right to left!
for (int j = target; j >= stone; j--) {
dp[j] = dp[j] || dp[j - stone];
}
}
// Find largest achievable sum
int maxSum = 0;
for (int j = target; j >= 0; j--) {
if (dp[j]) {
maxSum = j;
break;
}
}
return total - 2 * maxSum;
}
Why Right to Left? (CRITICAL!)
WRONG (left to right):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
for (int stone : stones) {
for (int j = stone; j <= target; j++) { // ❌ LEFT TO RIGHT
dp[j] = dp[j] || dp[j - stone];
}
}
Problem:
dp[5] = dp[5] || dp[5-stone] (updates dp[5])
dp[10] = dp[10] || dp[10-5] (uses NEW dp[5]!)
Same stone used TWICE! ✗
Violates 0/1 property!
RIGHT (right to left):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
for (int stone : stones) {
for (int j = target; j >= stone; j--) { // ✓ RIGHT TO LEFT
dp[j] = dp[j] || dp[j - stone];
}
}
Correct:
dp[10] = dp[10] || dp[5] (uses OLD dp[5])
dp[5] = ... (updates after)
Each stone used at most ONCE! ✓
Preserves 0/1 property!
SIMPLE RULE:
When reducing 2D → 1D in 0/1 knapsack,
ALWAYS process j from high to low!
📊 Complexity
Time: O(n × target)
Space: O(target) - Much better! ✓
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ LAST STONE WEIGHT II - 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 │
│ Boolean 2D │ O(n×sum) │ O(n×sum) │ Best ✓ │ Best ✓ │
│ Boolean 1D │ O(n×sum) │ O(sum) │ Great │ Optimal │
└──────────────┴───────────┴───────────┴────────────┴──────────┘
For interviews: Show progression from brute force to optimal!
💻 Complete Working Code
import java.util.Arrays;
class Solution {
public int lastStoneWeightII(int[] stones) {
return booleanDP1D(stones);
}
// Approach 4: Boolean DP 1D - O(n×sum) time, O(sum) space
private int booleanDP1D(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int stone : stones) {
for (int j = target; j >= stone; j--) {
dp[j] = dp[j] || dp[j - stone];
}
}
int maxSum = 0;
for (int j = target; j >= 0; j--) {
if (dp[j]) {
maxSum = j;
break;
}
}
return total - 2 * maxSum;
}
// Approach 3: Boolean DP 2D - O(n×sum) time, O(n×sum) space
private int booleanDP2D(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
int target = total / 2;
int n = stones.length;
boolean[][] dp = new boolean[n + 1][target + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= stones[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - stones[i - 1]];
}
}
}
int maxSum = 0;
for (int j = target; j >= 0; j--) {
if (dp[n][j]) {
maxSum = j;
break;
}
}
return total - 2 * maxSum;
}
// Approach 2: Memoization - O(n×sum) time, O(n×sum) space
private int[][] memo;
private int memoization(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
memo = new int[stones.length][total + 1];
for (int i = 0; i < stones.length; i++) {
Arrays.fill(memo[i], -1);
}
return helperMemo(stones, 0, 0, total);
}
private int helperMemo(int[] stones, int index, int sum1, int total) {
if (index == stones.length) {
int sum2 = total - sum1;
return Math.abs(sum1 - sum2);
}
if (memo[index][sum1] != -1) {
return memo[index][sum1];
}
int include = helperMemo(stones, index + 1, sum1 + stones[index], total);
int exclude = helperMemo(stones, index + 1, sum1, total);
int result = Math.min(include, exclude);
memo[index][sum1] = result;
return result;
}
// Approach 1: Brute Force - O(2^n) time
private int bruteForce(int[] stones) {
int total = 0;
for (int stone : stones) {
total += stone;
}
return helperBrute(stones, 0, 0, total);
}
private int helperBrute(int[] stones, int index, int sum1, int total) {
if (index == stones.length) {
int sum2 = total - sum1;
return Math.abs(sum1 - sum2);
}
int include = helperBrute(stones, index + 1, sum1 + stones[index], total);
int exclude = helperBrute(stones, index + 1, sum1, total);
return Math.min(include, exclude);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lastStoneWeightII(new int[] { 2, 7, 4, 1, 8, 1 }) == 1);
System.out.println(s.lastStoneWeightII(new int[] { 31, 26, 33, 21, 40 }) == 5);
System.out.println(s.lastStoneWeightII(new int[] { 2, 7, 4 }) == 1);
}
}
🔑 Key Insights
The Complete Journey
1. Discovery → Partition problem
2. Brute Force → Try all 2^n partitions
3. Memoization → Cache (index, sum1) states
4. Realization → Boolean DP simpler than integer
5. Bottom-Up 2D → Derive from memoization
6. Space Opt 1D → Only need previous row
Base Case Derivation
RECURSIVE → BOTTOM-UP mapping:
Recursive base:
if (index == n && sum == 0) return true;
if (index == n && sum > 0) return false;
Bottom-up base:
dp[0][0] = true ← "0 stones, sum 0"
dp[0][j>0] = false ← "0 stones, sum>0"
EXACT correspondence! ✓
Loop Bounds Explained
for (int i = 1; i <= n; i++)
WHY? Row 0 is base case, build from row 1
for (int j = 0; j <= target; j++)
WHY? Must include j=0 to propagate "sum 0 possible"
These come DIRECTLY from base case structure!
The Magic Formula
answer = total - 2×maxSum
WHY?
sum1 = maxSum (closest to total/2)
sum2 = total - maxSum
diff = |sum1 - sum2|
= |2×maxSum - total|
= total - 2×maxSum (since maxSum ≤ total/2)
🎪 Memory Aid
"Partition = Subset Sum!"
"dp[0][0] = true from recursive base!"
"i from 1 = build from base!"
"j from 0 = propagate sum 0!"
"Right to left = 0/1 property!" ✨
📝 Quick Revision Notes
🎯 Core Concept
Transform: Smashing → Partitioning → Subset Sum
Goal: Find largest achievable sum ≤ total/2
Formula: answer = total - 2×maxSum
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int lastStoneWeightII(int[] stones) {
// Key approach
// You have to divide all stones into 2 groups such that you need to minimize
// the absolute different of summation of these 2 groups.
// Aim is to minimize |s1- s2| which is in turn minimizing |s1-(total-s1)|
// which is again |2*s1-total|.
// Max minimum we get is 0 which is 2*s1-total=0 => s1 is total/2
// So, s1 should be as close to total/2 as possible or best case is total/2.
// Take every stone and try to keep that stone into either of these 2 groups and
// check the best result.
int total = Arrays.stream(stones).sum();
// // Start at index and sum of 1st group to be 0.
// return recursive(stones, 0, 0, total);
// Integer[][] memo = new Integer[stones.length][total + 1];
// return topDown(stones, 0, 0, total, memo);
return bottomUp(stones);
}
private int bottomUp(int[] stones) {
int len = stones.length;
int total = Arrays.stream(stones).sum();
int target = total / 2;
// can we make sum j using stones [0...i]?
boolean[][] dp = new boolean[len + 1][target + 1];
// step 1: base case
// can we make sum 0 with 0 stones? YES
dp[0][0] = true;
// dp[0][0...target]?
// can we make sum > 0 with 0 stones? NO => Hence, default FALSE.
// dp[0...len][0]?
// can we make sum = 0 with stones > 0? POSSIBLE. Hence, start from j = 0
// step 1.
// With above logics, start from i = 1 and sum = 1
for (int i = 1; i <= len; i++) {
for (int j = 0; j <= target; j++) {
boolean pick = false;
if (j - stones[i - 1] >= 0) {
pick = dp[i - 1][j - stones[i - 1]];
}
boolean no_pick = dp[i - 1][j];
dp[i][j] = pick || no_pick;
}
}
// step 2: find max weight that returns true
int maxSum = 0;
for (int j = target; j >= 0; j--) {
if (dp[len][j]) {
maxSum = j;
break;
}
}
return total - 2 * maxSum;
}
private int topDown(int[] stones, int index, int sum1, int total, Integer[][] memo) {
int res = total;
if (index == stones.length) {
int sum2 = total - sum1;
res = Math.min(res, Math.abs(sum1 - sum2));
return res;
}
if (memo[index][sum1] != null) {
return memo[index][sum1];
}
int pick = topDown(stones, index + 1, sum1 + stones[index], total, memo);
int no_pick = topDown(stones, index + 1, sum1, total, memo);
return memo[index][sum1] = Math.min(pick, no_pick);
}
private int recursive(int[] stones, int index, int sum1, int total) {
// step 1: max result we can achieve
int res = total;
// step 4: base case (all stones taken or consumed in the array)
if (index == stones.length) {
int sum2 = total - sum1;
res = Math.min(res, Math.abs(sum1 - sum2));
return res;
}
// step 2: pick the stone in group 1 (add it in sum1) and proceed to next index.
int pick = recursive(stones, index + 1, sum1 + stones[index], total);
// step 3: do not pick the stone in group 1 and proceed to next index.
int no_pick = recursive(stones, index + 1, sum1, total);
return Math.min(pick, no_pick);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lastStoneWeightII(new int[] { 2, 7, 4, 1, 8, 1 }) == 1);
System.out.println(s.lastStoneWeightII(new int[] { 31, 26, 33, 21, 40 }) == 5);
}
}
🔑 Base Case Checklist
- ✅ dp[0][0] = true (from recursive: no stones, sum 0)
- ✅ i starts from 1 (row 0 is base case)
- ✅ j starts from 0 (must propagate sum 0)
- ✅ Recurrence mirrors recursive pick/no-pick
- ✅ 1D version: process j right-to-left
🎉 Congratulations!
You've mastered the COMPLETE progression: - ✅ Discovery through examples - ✅ Brute force with full dry run - ✅ Memoization with full dry run - ✅ WHY boolean DP transformation - ✅ Bottom-up 2D with ELI5 base cases - ✅ Space optimization to 1D - ✅ Complete understanding of EVERY detail!
You can now derive bottom-up from recursive for ANY problem! 🚀✨