Last Stone Weight II

🎯

Last Stone Weight II

mediumDPGoogleAmazon

Imagine you have a collection of stones with different weights. You want to smash them together in pairs to minimize the weight of the last remaining stone.

💡 This problem is a classic example of partitioning a set into two subsets to minimize the difference of their sums. Beginners often struggle because it looks like a greedy problem but requires dynamic programming to handle all combinations efficiently.

📋

Problem Statement

Given an array stones where stones[i] is the weight of the ith stone, you smash stones together. Each smash combines two stones with weights x and y, resulting in either no stone if x == y or a new stone with weight |x - y| if x != y. Return the smallest possible weight of the last stone (or 0 if none remain) after smashing the stones optimally.

1 ≤ stones.length ≤ 301 ≤ stones[i] ≤ 100

💡

Example

Input"[2,7,4,1,8,1]"

Output1

One optimal sequence leads to a last stone weight of 1.

• Single stone → output is the stone's weight
• All stones have the same weight → output is 0
• Two stones with different weights → output is their absolute difference
• Large number of stones with small weights → tests efficiency

🔁

Why DP?

Why greedy fails:

Greedy fails because smashing the heaviest stones first does not guarantee minimal last stone weight. For example, stones = [2,7,4,1,8,1], greedy smashing largest stones first leads to suboptimal results.

DP state:

dp[i][w] = True if it is possible to achieve a subset sum w using the first i stones.

Recurrence:dp[i][w] = dp[i-1][w] or dp[i-1][w - stones[i-1]] if w >= stones[i-1]

For each stone, either we don't include it (dp[i-1][w]) or include it if possible (dp[i-1][w - stone weight]).

⚠️

Common Mistakes

Using greedy approach to always smash largest stones first

Leads to incorrect minimal last stone weight

✅ Use DP to consider all subset partitions

Not iterating backwards in space optimized DP

Counts stones multiple times, producing wrong results

✅ Iterate sums from high to low to preserve 0/1 knapsack constraints

Forgetting to initialize dp[0][0] = True in tabulation

No sums are marked achievable, DP fails

✅ Initialize dp[0][0] = True to represent sum zero achievable with zero stones

Using difference as DP state in memoization without normalization

Memo keys become large and inefficient, causing TLE

✅ Use subset sum approach or limit difference range

Not handling edge cases like single stone or all equal stones

Incorrect output or runtime errors

✅ Add checks or rely on DP base cases to handle these

🧠

Brute Force (Pure Recursion)

💡 Brute force helps understand the problem by exploring all possible partitions of stones into two groups, but it is inefficient due to exponential time complexity.

Intuition

Try all ways to assign each stone to one of two piles and compute the minimal difference of their sums.

Algorithm

1. Define a recursive function that tries placing each stone in either of two subsets.
2. At each step, recurse with updated sums for both subsets.
3. When all stones are assigned, compute the absolute difference of sums.
4. Return the minimal difference found among all assignments.

💡 This approach is conceptually simple but inefficient because it explores all 2^n assignments.

Recurrence:f(i, sum1, sum2) = min(f(i+1, sum1 + stones[i], sum2), f(i+1, sum1, sum2 + stones[i]))

</>

Code

def lastStoneWeightII(stones):
    n = len(stones)
    def dfs(i, sum1, sum2):
        if i == n:
            return abs(sum1 - sum2)
        left = dfs(i + 1, sum1 + stones[i], sum2)
        right = dfs(i + 1, sum1, sum2 + stones[i])
        return min(left, right)

    return dfs(0, 0, 0)

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))

Line Notes

def dfs(i, sum1, sum2):Defines recursive helper to explore subsets

if i == n:Base case: all stones assigned

return abs(sum1 - sum2)Compute difference when all stones assigned

left = dfs(i + 1, sum1 + stones[i], sum2)Assign current stone to first subset

right = dfs(i + 1, sum1, sum2 + stones[i])Assign current stone to second subset

return min(left, right)Choose minimal difference from both assignments

import java.util.*;
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        return dfs(stones, 0, 0, 0);
    }
    private int dfs(int[] stones, int i, int sum1, int sum2) {
        if (i == stones.length) {
            return Math.abs(sum1 - sum2);
        }
        int left = dfs(stones, i + 1, sum1 + stones[i], sum2);
        int right = dfs(stones, i + 1, sum1, sum2 + stones[i]);
        return Math.min(left, right);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}

Line Notes

public int lastStoneWeightII(int[] stones)Entry point for solution

if (i == stones.length)Base case: all stones assigned

return Math.abs(sum1 - sum2)Calculate difference at leaf

int left = dfs(...)Assign stone to first subset

int right = dfs(...)Assign stone to second subset

return Math.min(left, right)Choose minimal difference

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        return dfs(stones, 0, 0, 0);
    }
private:
    int dfs(vector<int>& stones, int i, int sum1, int sum2) {
        if (i == stones.size()) {
            return abs(sum1 - sum2);
        }
        int left = dfs(stones, i + 1, sum1 + stones[i], sum2);
        int right = dfs(stones, i + 1, sum1, sum2 + stones[i]);
        return min(left, right);
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}

Line Notes

int dfs(vector<int>& stones, int i, int sum1, int sum2)Recursive helper exploring subsets

if (i == stones.size())Base case: all stones assigned

return abs(sum1 - sum2)Calculate difference at leaf

int left = dfs(...)Assign stone to first subset

int right = dfs(...)Assign stone to second subset

return min(left, right)Choose minimal difference

function lastStoneWeightII(stones) {
    const n = stones.length;
    function dfs(i, sum1, sum2) {
        if (i === n) return Math.abs(sum1 - sum2);
        const left = dfs(i + 1, sum1 + stones[i], sum2);
        const right = dfs(i + 1, sum1, sum2 + stones[i]);
        return Math.min(left, right);
    }
    return dfs(0, 0, 0);
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));

Line Notes

function dfs(i, sum1, sum2)Recursive helper to explore subsets

if (i === n)Base case: all stones assigned

return Math.abs(sum1 - sum2)Calculate difference at leaf

const left = dfs(...)Assign stone to first subset

const right = dfs(...)Assign stone to second subset

return Math.min(left, right)Choose minimal difference

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each stone has two choices, leading to 2^n combinations.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down Memoization (Recursion + Caching)

💡 Memoization avoids recomputing the same states by caching results, drastically improving efficiency over brute force.

Intuition

Store results of subproblems defined by current index and sum difference to avoid repeated work.

Algorithm

1. Define a recursive function with parameters for current index and current sum.
2. Use a dictionary or map to cache results for each (index, sum) pair.
3. If a state is cached, return it immediately.
4. Otherwise, recurse by including or excluding the current stone and cache the minimal difference.

💡 Memoization reduces exponential calls to polynomial by remembering results.

Recurrence:f(i, sum) = min(f(i+1, sum + stones[i]), f(i+1, abs(sum - stones[i])))

</>

Code

def lastStoneWeightII(stones):
    from functools import lru_cache
    n = len(stones)

    @lru_cache(None)
    def dfs(i, diff):
        if i == n:
            return diff
        left = dfs(i + 1, diff + stones[i])
        right = dfs(i + 1, abs(diff - stones[i]))
        return min(left, right)

    return dfs(0, 0)

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))

Line Notes

@lru_cache(None)Caches results of dfs calls to avoid recomputation

def dfs(i, diff):Recursive function with current index and difference

if i == n:Base case: all stones processed

return diffReturn current difference

left = dfs(i + 1, diff + stones[i])Add current stone weight to difference

right = dfs(i + 1, abs(diff - stones[i]))Subtract current stone weight from difference

return min(left, right)Choose minimal difference

import java.util.*;
public class Solution {
    private int[] stones;
    private Map<String, Integer> memo = new HashMap<>();
    public int lastStoneWeightII(int[] stones) {
        this.stones = stones;
        return dfs(0, 0);
    }
    private int dfs(int i, int diff) {
        if (i == stones.length) return diff;
        String key = i + "," + diff;
        if (memo.containsKey(key)) return memo.get(key);
        int left = dfs(i + 1, diff + stones[i]);
        int right = dfs(i + 1, Math.abs(diff - stones[i]));
        int res = Math.min(left, right);
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}

Line Notes

private Map<String, Integer> memoCache for storing computed states

String key = i + "," + diff;Unique key for memoization

if (memo.containsKey(key))Return cached result if available

int left = dfs(...)Add stone weight to difference

int right = dfs(...)Subtract stone weight from difference

memo.put(key, res);Store computed result

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <cmath>
using namespace std;

class Solution {
    vector<int> stones;
    unordered_map<string, int> memo;
public:
    int lastStoneWeightII(vector<int>& stones) {
        this->stones = stones;
        return dfs(0, 0);
    }
private:
    int dfs(int i, int diff) {
        if (i == stones.size()) return diff;
        string key = to_string(i) + "," + to_string(diff);
        if (memo.count(key)) return memo[key];
        int left = dfs(i + 1, diff + stones[i]);
        int right = dfs(i + 1, abs(diff - stones[i]));
        int res = min(left, right);
        memo[key] = res;
        return res;
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache for memoization

string key = to_string(i) + "," + to_string(diff);Unique key for state

if (memo.count(key))Return cached result if exists

int left = dfs(...)Add stone weight to difference

int right = dfs(...)Subtract stone weight from difference

memo[key] = res;Store computed result

function lastStoneWeightII(stones) {
    const n = stones.length;
    const memo = new Map();
    function dfs(i, diff) {
        if (i === n) return diff;
        const key = i + ',' + diff;
        if (memo.has(key)) return memo.get(key);
        const left = dfs(i + 1, diff + stones[i]);
        const right = dfs(i + 1, Math.abs(diff - stones[i]));
        const res = Math.min(left, right);
        memo.set(key, res);
        return res;
    }
    return dfs(0, 0);
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));

Line Notes

const memo = new Map();Cache for memoization

const key = i + ',' + diff;Unique key for state

if (memo.has(key))Return cached result if exists

const left = dfs(...)Add stone weight to difference

const right = dfs(...)Subtract stone weight from difference

memo.set(key, res);Store computed result

⏱

Complexity

TimeO(n * sum)

SpaceO(n * sum) due to memoization cache and recursion stack

Memoization reduces exponential calls to polynomial by caching states defined by index and difference.

💡 For n=30 and sum=1500, this is feasible with pruning and caching.

Interview Verdict: Accepted

This approach is efficient enough for the problem constraints and is a good intermediate step.

🧠

Bottom-Up Tabulation (0/1 Knapsack DP)

💡 Tabulation builds the solution iteratively, which is often easier to debug and understand than recursion with memoization.

Intuition

Use a boolean DP table to track which subset sums are achievable with the first i stones, then find the closest sum to half the total weight.

Algorithm

1. Calculate total sum of stones.
2. Initialize a 2D boolean DP array dp[n+1][total_sum//2 + 1].
3. dp[i][w] = True if sum w is achievable using first i stones.
4. Fill dp iteratively using the recurrence relation.
5. Find the largest w where dp[n][w] is True, then minimal difference is total_sum - 2*w.

💡 This approach systematically builds all achievable sums and finds the best partition.

Recurrence:dp[i][w] = dp[i-1][w] or dp[i-1][w - stones[i-1]] if w >= stones[i-1]

</>

Code

def lastStoneWeightII(stones):
    total = sum(stones)
    n = len(stones)
    half = total // 2
    dp = [[False] * (half + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
        weight = stones[i - 1]
        for w in range(half + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= weight:
                dp[i][w] = dp[i][w] or dp[i - 1][w - weight]

    for w in range(half, -1, -1):
        if dp[n][w]:
            return total - 2 * w

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))

Line Notes

total = sum(stones)Calculate total weight to find half

dp = [[False] * (half + 1) for _ in range(n + 1)]Initialize DP table for sums

dp[0][0] = TrueSum 0 is achievable with 0 stones

for i in range(1, n + 1):Iterate over stones

dp[i][w] = dp[i - 1][w]Exclude current stone

if w >= weight:Check if current stone can be included

dp[i][w] = dp[i][w] or dp[i - 1][w - weight]Include current stone if possible

for w in range(half, -1, -1):Find closest achievable sum to half

import java.util.*;
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int n = stones.length;
        int half = total / 2;
        boolean[][] dp = new boolean[n + 1][half + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int weight = stones[i - 1];
            for (int w = 0; w <= half; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= weight) dp[i][w] = dp[i][w] || dp[i - 1][w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[n][w]) return total - 2 * w;
        }
        return 0;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}

Line Notes

int total = 0;Calculate total weight

boolean[][] dp = new boolean[n + 1][half + 1];DP table for achievable sums

dp[0][0] = true;Sum 0 achievable with 0 stones

for (int i = 1; i <= n; i++)Iterate stones

dp[i][w] = dp[i - 1][w];Exclude current stone

if (w >= weight)Check if stone can be included

dp[i][w] = dp[i][w] || dp[i - 1][w - weight];Include stone if possible

for (int w = half; w >= 0; w--)Find closest sum to half

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = 0;
        for (int s : stones) total += s;
        int n = stones.size();
        int half = total / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(half + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int weight = stones[i - 1];
            for (int w = 0; w <= half; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= weight) dp[i][w] = dp[i][w] || dp[i - 1][w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[n][w]) return total - 2 * w;
        }
        return 0;
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}

Line Notes

int total = 0;Calculate total weight

vector<vector<bool>> dp(n + 1, vector<bool>(half + 1, false));DP table for sums

dp[0][0] = true;Sum 0 achievable with no stones

for (int i = 1; i <= n; i++)Iterate stones

dp[i][w] = dp[i - 1][w];Exclude current stone

if (w >= weight)Check if stone can be included

dp[i][w] = dp[i][w] || dp[i - 1][w - weight];Include stone if possible

for (int w = half; w >= 0; w--)Find closest sum to half

function lastStoneWeightII(stones) {
    const total = stones.reduce((a, b) => a + b, 0);
    const n = stones.length;
    const half = Math.floor(total / 2);
    const dp = Array.from({ length: n + 1 }, () => Array(half + 1).fill(false));
    dp[0][0] = true;

    for (let i = 1; i <= n; i++) {
        const weight = stones[i - 1];
        for (let w = 0; w <= half; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weight) dp[i][w] = dp[i][w] || dp[i - 1][w - weight];
        }
    }

    for (let w = half; w >= 0; w--) {
        if (dp[n][w]) return total - 2 * w;
    }
    return 0;
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));

Line Notes

const total = stones.reduce((a, b) => a + b, 0);Calculate total weight

const dp = Array.from({ length: n + 1 }, () => Array(half + 1).fill(false));DP table for sums

dp[0][0] = true;Sum 0 achievable with no stones

for (let i = 1; i <= n; i++)Iterate stones

dp[i][w] = dp[i - 1][w];Exclude current stone

if (w >= weight)Check if stone can be included

dp[i][w] = dp[i][w] || dp[i - 1][w - weight];Include stone if possible

for (let w = half; w >= 0; w--)Find closest sum to half

⏱

Complexity

TimeO(n * sum)

SpaceO(n * sum)

We fill a DP table with n rows and sum/2 columns.

💡 For n=30 and sum=1500, this is efficient and practical.

Interview Verdict: Accepted

This is the standard optimal DP solution for this problem.

🧠

Space Optimized Bottom-Up DP (1D Array)

💡 We can reduce space from O(n*sum) to O(sum) by using a 1D DP array and iterating backwards over sums.

Intuition

Track achievable sums with a single array, updating from high to low to avoid reuse of stones in the same iteration.

Algorithm

1. Calculate total sum and half.
2. Initialize a 1D boolean dp array of size half+1 with dp[0] = True.
3. For each stone, iterate sums backwards from half to stone weight.
4. Update dp[w] |= dp[w - stone] to mark achievable sums.
5. Find the largest w where dp[w] is True and return total - 2*w.

💡 Backward iteration ensures stones are counted once per iteration, preserving 0/1 knapsack constraints.

Recurrence:dp[w] = dp[w] or dp[w - stones[i]] if w >= stones[i]

</>

Code

def lastStoneWeightII(stones):
    total = sum(stones)
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True

    for weight in stones:
        for w in range(half, weight - 1, -1):
            dp[w] = dp[w] or dp[w - weight]

    for w in range(half, -1, -1):
        if dp[w]:
            return total - 2 * w

# Driver code
if __name__ == '__main__':
    stones = [2,7,4,1,8,1]
    print(lastStoneWeightII(stones))

Line Notes

dp = [False] * (half + 1)Initialize 1D DP array for sums

dp[0] = TrueSum 0 achievable with no stones

for w in range(half, weight - 1, -1)Iterate backwards to avoid reuse

dp[w] = dp[w] or dp[w - weight]Update achievable sums including current stone

for w in range(half, -1, -1)Find closest achievable sum to half

import java.util.*;
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int s : stones) total += s;
        int half = total / 2;
        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        for (int weight : stones) {
            for (int w = half; w >= weight; w--) {
                dp[w] = dp[w] || dp[w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[w]) return total - 2 * w;
        }
        return 0;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] stones = {2,7,4,1,8,1};
        System.out.println(sol.lastStoneWeightII(stones));
    }
}

Line Notes

boolean[] dp = new boolean[half + 1];1D DP array for sums

dp[0] = true;Sum 0 achievable with no stones

for (int w = half; w >= weight; w--)Backward iteration to avoid reuse

dp[w] = dp[w] || dp[w - weight];Update achievable sums

for (int w = half; w >= 0; w--)Find closest sum to half

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = 0;
        for (int s : stones) total += s;
        int half = total / 2;
        vector<bool> dp(half + 1, false);
        dp[0] = true;
        for (int weight : stones) {
            for (int w = half; w >= weight; w--) {
                dp[w] = dp[w] || dp[w - weight];
            }
        }
        for (int w = half; w >= 0; w--) {
            if (dp[w]) return total - 2 * w;
        }
        return 0;
    }
};

int main() {
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};
    cout << sol.lastStoneWeightII(stones) << endl;
    return 0;
}

Line Notes

vector<bool> dp(half + 1, false);1D DP array for sums

dp[0] = true;Sum 0 achievable with no stones

for (int w = half; w >= weight; w--)Backward iteration to avoid reuse

dp[w] = dp[w] || dp[w - weight];Update achievable sums

for (int w = half; w >= 0; w--)Find closest sum to half

function lastStoneWeightII(stones) {
    const total = stones.reduce((a, b) => a + b, 0);
    const half = Math.floor(total / 2);
    const dp = new Array(half + 1).fill(false);
    dp[0] = true;

    for (const weight of stones) {
        for (let w = half; w >= weight; w--) {
            dp[w] = dp[w] || dp[w - weight];
        }
    }

    for (let w = half; w >= 0; w--) {
        if (dp[w]) return total - 2 * w;
    }
    return 0;
}

// Test
console.log(lastStoneWeightII([2,7,4,1,8,1]));

Line Notes

const dp = new Array(half + 1).fill(false);1D DP array for sums

dp[0] = true;Sum 0 achievable with no stones

for (let w = half; w >= weight; w--)Backward iteration to avoid reuse

dp[w] = dp[w] || dp[w - weight];Update achievable sums

for (let w = half; w >= 0; w--)Find closest sum to half

⏱

Complexity

TimeO(n * sum)

SpaceO(sum)

We use a single DP array of size sum/2 and update it for each stone.

💡 This is the most space-efficient DP solution practical for interviews.

Interview Verdict: Accepted

This is the best practical solution balancing time and space.

📊

All Approaches - One-Glance Tradeoffs

💡 Use space optimized DP in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes	Yes	Mention only - never code
2. Top-Down Memoization	O(n * sum)	O(n * sum)	Possible but less likely	Yes	Good intermediate solution
3. Bottom-Up Tabulation	O(n * sum)	O(n * sum)	No	Yes	Optimal DP solution
4. Space Optimized DP	O(n * sum)	O(sum)	No	Harder but possible	Best practical solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify problem constraints and examples.Explain brute force to show understanding of problem structure.Introduce memoization to optimize brute force.Present bottom-up DP as optimal solution.Mention space optimization if time permits.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of subset sum and partitioning, ability to optimize brute force with DP, and coding skills for DP tabulation.

Common Follow-ups

• What if stones array is very large? → Use space optimized DP or approximate algorithms.
• Can you reconstruct the subsets? → Yes, by tracking choices in DP table.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves partitioning or subset sums; 2) Minimize difference between two groups; 3) 0/1 knapsack style constraints; 4) Need to consider all subsets.

Signature Phrases

'partition stones into two groups''minimize the weight difference''subset sum closest to half'

NOT This Pattern When

Greedy or sorting based problems that do not require subset sum or DP.

Similar Problems

Partition Equal Subset Sum - same subset sum DP approachTarget Sum - similar DP with sign assignmentsMinimum Subset Sum Difference - direct minimization of subset difference

Practice

1. Consider the following code for integer break. What is the value of dp[3] after the outer loop iteration i = 3 completes?

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

print(integer_break(4))  # Output not asked here

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Trace dp for i=2

   dp[1] = 1 (given). For i=2, j=1: max_product = max(0, max(1,1)*max(1,1)) = 1, so dp[2] = 1.

2. Step 2: Trace dp for i=3

   j=1: max_product = max(0, max(1,1)*max(2,dp[2])) = max(0,1*2) = 2 j=2: max_product = max(2, max(2,dp[2])*max(1,dp[1])) = max(2,2*1) = 2 So dp[3] = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[3] = 2 matches manual calculation [OK]

Hint: Trace inner loop carefully for each j [OK]

Common Mistakes:

• Off-by-one in loop bounds
• Confusing dp[i-j] with dp[j]

2. The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 11: Using bisect_right to find compatible job index

B. Line 7: Creating ends array from job end times

C. Line 4: Sorting jobs by start time instead of end time

D. Line 14: Calculating dp[i] as max of take and skip

Solution

1. Step 1: Identify sorting criteria

   Jobs must be sorted by end time for binary search on ends array to work correctly.

2. Step 2: Check sorting line

   Line 4 sorts by start time, breaking DP dependencies and binary search correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]

Hint: Sort jobs by end time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Incorrect binary search bounds
• Ignoring dp base cases

3. Identify the bug in the following code snippet for counting ways to make change using 1D DP:

def count_ways_bug(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for w in range(amount, coin - 1, -1):
            dp[w] += dp[w - coin]
    return dp[amount]

What is the bug?

medium

A. dp[0] should be initialized to 1, not 0

B. The inner loop should iterate forwards from coin to amount, not backwards

C. The dp array size should be amount, not amount + 1

D. The return statement should return dp[0] instead of dp[amount]

Solution

1. Step 1: Check base case initialization

   dp[0] represents ways to make amount 0, which must be 1 (empty combination), but here it is set to 0, causing all dp values to remain 0.

2. Step 2: Verify loop direction

   Though iterating backwards is incorrect for unlimited coin usage, the critical bug causing zero results is dp[0] initialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct base case dp[0]=1 is essential for counting ways [OK]

Hint: dp[0] must be 1 to count empty combination [OK]

Common Mistakes:

• Initializing dp[0] to 0 misses base case
• Iterating amounts backwards in 1D DP misses combinations
• Incorrect dp array size causes index errors

4. What is the time complexity of the bottom-up dynamic programming solution for the Perfect Squares problem using the unbounded knapsack pattern, where n is the input number?

medium

A. O(n^2)

B. O(sqrt(n) * log n)

C. O(n * log n)

D. O(n * sqrt(n))

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs from 1 to n (O(n)). The inner loop iterates over all perfect squares less than or equal to i, which is approximately O(sqrt(n)) because the largest square root is about sqrt(n).

2. Step 2: Combine complexities

   Multiplying outer and inner loops gives O(n * sqrt(n)). Other options either overestimate (O(n^2)) or underestimate (O(n log n), O(sqrt(n) log n)) the complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops: n and sqrt(n) -> O(n * sqrt(n)) [OK]

Hint: Inner loop runs up to sqrt(n), outer up to n [OK]

Common Mistakes:

• Assuming inner loop is O(n)
• Confusing recursion stack space with DP space

5. Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?

hard

A. Change the inner loop to iterate forwards from num to S, allowing reuse of the same number multiple times.

B. Keep the inner loop iterating backwards from S to num, as in the 0/1 subset sum problem.

C. Use a recursive brute force approach without memoization to handle multiple uses.

D. Sort the input array and apply a greedy approach picking largest numbers first.

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   In unbounded knapsack, items can be reused multiple times, so dp updates must allow reuse within the same iteration.

2. Step 2: Modify iteration direction

   Iterating forwards allows dp[w] to use dp[w - num] updated in the same iteration, enabling multiple uses of num.

3. Step 3: Confirm correctness

   Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded variant.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward iteration enables multiple uses -> correct for unbounded knapsack [OK]

Hint: Unbounded knapsack requires forward iteration to allow reuse [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack
• Trying greedy or brute force without memoization