Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Last Stone Weight II solution and explanation

MediumArrayDynamic Programming6 min read61.2% acceptanceUpdated 9 Apr 2026
Asked atGoogleAmazonMicrosoftMetaBloomberg
Practise Last Stone Weight II
19:04
Last Stone Weight II - Leetcode 1049 - PythonNeetCodeIO · 19:04 · 33K viewsWatch on YouTube
9 more videos on this problem
  1. Last Stone Weight II - Leetcode 1049 - PythonNeetCodeIO · 19:04 · 33K views
  2. LeetCode - Last Stone Weight 2 (1049)Kshittiz K · 18:52 · 10K views
  3. Leetcode--1049 last stone weight ii (DP)You Wu · 15:20 · 4K views
  4. 【每日一题】1049 Last Stone Weight II, 05/29/2019Huifeng Guan · 26:51 · 3K views
  5. Lecture 21 : Last Stone Weight II | Recursion | Memoization | Tabulation | DP PYAR HAICODE SHARK · 24:39 · 2K views
  6. LeetCode 1049 | Last Stone Weight II | Knapsack | JavaSleepy Cracker · 12:52 · 2K views
  7. Leetcode 1049. Last Stone Weight II (01 knapsack)LetsCode · 6:29 · 543 views
  8. 1049. Last Stone Weight IIAlgorithms for Big Bucks · 11:32 · 358 views
  9. 205. leetcode 1049. Last Stone Weight II : JAVAWeb Fusion with Bharadwaj · 14:07 · 298 views
  10. Last Stone Weight II - Dynamic Programming - Leetcode 1049 - JAVA || DP Series || Qsn 10codewithme · 17:58 · 68 views

The problem

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 weight x is destroyed, and the stone of weight y has new weight y - 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
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:

Input: stones = [31,26,33,21,40]
Output: 5

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

Approach overview

Problem Overview: You are given an array of stone weights. Each turn you smash two stones together; equal weights destroy both, otherwise the heavier one becomes the difference. The goal is to minimize the final remaining weight after all possible smashes.

The key observation: smashing stones is equivalent to partitioning the stones into two groups whose total weights are as close as possible. If one group has sum S1 and the other S2, the final weight becomes |S1 - S2|. The task reduces to finding a subset whose sum is as close as possible to half of the total weight.

Approach 1: Backtracking with Memoization (Time: O(n * sum), Space: O(n * sum))

This approach explores all ways to assign each stone to one of two groups. At index i, you decide whether to add the stone weight to the current subset or skip it. Without optimization, this forms a binary decision tree with 2^n states. Memoization stores results for states defined by (index, currentSum), avoiding repeated work.

The recursion tries to build a subset sum as close as possible to total/2. When all stones are processed, compute the difference between the two partitions. Memoization drastically reduces the search space because many recursive paths reach the same state. This approach is useful when demonstrating the transition from brute-force recursion to optimized dynamic programming and reinforces how overlapping subproblems appear in dynamic programming.

Approach 2: Dynamic Programming (Subset Sum / Knapsack) (Time: O(n * sum), Space: O(sum))

The optimal approach models the problem as a classic 0/1 knapsack variant. Compute the total weight of all stones and target half = total / 2. The goal is to find the largest achievable subset sum that does not exceed half.

Create a DP array where dp[s] indicates whether a subset sum s is achievable. Iterate through the stones and update the DP array in reverse order so each stone is used at most once. For every weight w, update dp[s] = dp[s] OR dp[s - w]. After processing all stones, scan from half downward to find the largest achievable sum.

If the best subset sum is best, the final answer becomes total - 2 * best. This works because the other partition automatically contains the remaining weight. The approach runs in linear time relative to the number of stones and the total sum, making it efficient for typical constraints. It also demonstrates a practical use of subset partitioning with arrays and state transitions commonly used in array processing problems.

Recommended for interviews: The dynamic programming subset-sum solution is the expected answer. Interviewers want to see the reduction from stone smashing to partition difference and then the application of a knapsack-style DP. Mentioning the recursive backtracking idea shows problem exploration, but implementing the optimized DP demonstrates strong mastery of dynamic programming patterns.

Approach 1: Dynamic Programming Approach

The problem can be thought of as partitioning the stones into two groups with a minimum difference in their total weights. This is similar to a variant of the knapsack problem where we try to fill a knapsack with maximum capacity, close to half of the total sum of stones.

Using dynamic programming, we define a state dp[j] which is true if a sum j can be achieved with the given stones. We traverse through the stones, updating our achievable sums. Finally, we find the largest sum that can be achieved which is less than or equal to half of the total sum of all stones. The answer will be the total sum minus twice this value.

def lastStoneWeightII(stones):
    total_sum = sum(stones)
    half_sum = total_sum // 2
    dp = [False] * (half_sum + 1)
    dp[0] = True
    for stone in stones:
        for j in range(half_sum, stone - 1, -1):
            dp[j] = dp[j] or dp[j - stone]
    for j in range(half_sum, -1, -1):
        if dp[j]:
            return total_sum - 2 * j
    return 0
public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) sum += stone; 
        int halfSum = sum / 2;
        boolean[] dp = new boolean[halfSum + 1];
        dp[0] = true;
        for (int stone : stones) {
            for (int j = halfSum; j >= stone; --j) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        for (int j = halfSum; j >= 0; --j) {
            if (dp[j]) return sum - 2 * j;
        }
        return 0;
    }
}
#include <vector>
#include <iostream>

int lastStoneWeightII(std::vector<int>& stones) {
    int sum = 0;
    for (auto s : stones) sum += s;
    int halfSum = sum / 2;
    std::vector<bool> dp(halfSum + 1, false);
    dp[0] = true;
    for (auto &stone : stones) {
        for (int j = halfSum; j >= stone; --j) {
            dp[j] = dp[j] || dp[j - stone];
        }
    }
    for (int j = halfSum; j >= 0; --j) {
        if (dp[j]) return sum - 2 * j;
    }
    return 0;
}
function lastStoneWeightII(stones) {
    const sum = stones.reduce((acc, stone) => acc + stone, 0);
    const halfSum = Math.floor(sum / 2);
    const dp = new Array(halfSum + 1).fill(false);
    dp[0] = true;
    stones.forEach(stone => {
        for (let j = halfSum; j >= stone; --j) {
            dp[j] = dp[j] || dp[j - stone];
        }
    });
    for (let j = halfSum; j >= 0; --j) {
        if (dp[j]) return sum - 2 * j;
    }
    return 0;
}
#include <stdio.h>
#include <stdbool.h>

int lastStoneWeightII(int* stones, int stonesSize) {
    int sum = 0;
    for (int i = 0; i < stonesSize; ++i) sum += stones[i];
    int halfSum = sum / 2;
    bool dp[1501] = { false };
    dp[0] = true;
    for (int i = 0; i < stonesSize; ++i) {
        for (int j = halfSum; j >= stones[i]; --j) {
            dp[j] |= dp[j - stones[i]];
        }
    }
    for (int j = halfSum; j >= 0; --j) {
        if (dp[j]) return sum - 2 * j;
    }
    return 0;
}
public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int totalSum = stones.Sum();
        int halfSum = totalSum / 2;
        bool[] dp = new bool[halfSum + 1];
        dp[0] = true;
        foreach (int stone in stones) {
            for (int j = halfSum; j >= stone; --j) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        for (int j = halfSum; j >= 0; --j) {
            if (dp[j]) return totalSum - 2 * j;
        }
        return 0;
    }
}

The Python implementation relies on a similar dynamic programming solution, focusing on achievable sums. With the help of a boolean array, and iterating from the desired sum downwards, we determine the smallest possible last stone weight through achievable sub-sums.

Complexity

Time Complexity: O(n * sum/2)
Space Complexity: O(sum/2)

Try this approach in the editor

Approach 2: Backtracking with Memoization Approach

Another approach to solve the Last Stone Weight II problem is by using backtracking with memoization. In this approach, we try to partition the stones into two sets where the difference between the total weights of the two sets is minimized. We can recursively explore all combinations of partitioned stones while keeping track of their sums.

To optimize, we use memoization to store and reuse the results of already calculated differences for sub-problems, reducing redundant calculations and improving performance.

def lastStoneWeightII(stones):
    def helper(index, sum1, sum2):
        if index == len(stones):
            return abs(sum1 - sum2)
        if memo[index][sum1] is not None:
            return memo[index][sum1]
        diff1 = helper(index + 1, sum1 + stones[index], sum2)
        diff2 = helper(index + 1, sum1, sum2 + stones[index])
        memo[index][sum1] = min(diff1, diff2)
        return memo[index][sum1]
    total_sum = sum(stones)
    memo = [[None] * (total_sum + 1) for _ in range(len(stones))]
    return helper(0, 0, 0)
import java.util.Arrays;

public class Solution {
    private int helper(int[] stones, int index, int sum1, int sum2, int[][] memo) {
        if (index == stones.length) {
            return Math.abs(sum1 - sum2);
        }
        if (memo[index][sum1] != -1) {
            return memo[index][sum1];
        }
        int diff1 = helper(stones, index + 1, sum1 + stones[index], sum2, memo);
        int diff2 = helper(stones, index + 1, sum1, sum2 + stones[index], memo);
        memo[index][sum1] = Math.min(diff1, diff2);
        return memo[index][sum1];
    }

    public int lastStoneWeightII(int[] stones) {
        int totalSum = Arrays.stream(stones).sum();
        int[][] memo = new int[stones.length][totalSum + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return helper(stones, 0, 0, 0, memo);
    }
}
#include <vector>
#include <cmath>
#include <algorithm>

int helper(std::vector<int>& stones, int index, int sum1, int sum2, std::vector<std::vector<int>>& memo) {
    if (index == stones.size()) {
        return std::abs(sum1 - sum2);
    }
    if (memo[index][sum1] != -1) {
        return memo[index][sum1];
    }
    int diff1 = helper(stones, index + 1, sum1 + stones[index], sum2, memo);
    int diff2 = helper(stones, index + 1, sum1, sum2 + stones[index], memo);
    memo[index][sum1] = std::min(diff1, diff2);
    return memo[index][sum1];
}

int lastStoneWeightII(std::vector<int>& stones) {
    int totalSum = 0;
    for (int stone : stones) totalSum += stone;
    std::vector<std::vector<int>> memo(stones.size(), std::vector<int>(totalSum + 1, -1));
    return helper(stones, 0, 0, 0, memo);
}
function lastStoneWeightII(stones) {
    const helper = (index, sum1, sum2) => {
        if (index === stones.length) {
            return Math.abs(sum1 - sum2);
        }
        const key = `${index},${sum1}`;
        if (key in memo) {
            return memo[key];
        }
        const diff1 = helper(index + 1, sum1 + stones[index], sum2);
        const diff2 = helper(index + 1, sum1, sum2 + stones[index]);
        memo[key] = Math.min(diff1, diff2);
        return memo[key];
    };
    const totalSum = stones.reduce((acc, stone) => acc + stone, 0);
    const memo = {};
    return helper(0, 0, 0);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int helper(int* stones, int stonesSize, int currentIndex, int sum1, int sum2, int** memo) {
    if (currentIndex == stonesSize) {
        return abs(sum1 - sum2);
    }
    if (memo[currentIndex][sum1] != -1) {
        return memo[currentIndex][sum1];
    }
    int diff1 = helper(stones, stonesSize, currentIndex + 1, sum1 + stones[currentIndex], sum2, memo);
    int diff2 = helper(stones, stonesSize, currentIndex + 1, sum1, sum2 + stones[currentIndex], memo);
    memo[currentIndex][sum1] = fmin(diff1, diff2);
    return memo[currentIndex][sum1];
}

int lastStoneWeightII(int* stones, int stonesSize) {
    int totalSum = 0;
    for (int i = 0; i < stonesSize; ++i) totalSum += stones[i];
    int** memo = (int**)malloc(stonesSize * sizeof(int*));
    for (int i = 0; i < stonesSize; ++i) {
        memo[i] = (int*)malloc((totalSum + 1) * sizeof(int));
        memset(memo[i], -1, (totalSum + 1) * sizeof(int));
    }
    int result = helper(stones, stonesSize, 0, 0, 0, memo);
    for (int i = 0; i < stonesSize; ++i) free(memo[i]);
    free(memo);
    return result;
}
using System;

public class Solution {
    private int Helper(int[] stones, int index, int sum1, int sum2, int[,] memo) {
        if (index == stones.Length) {
            return Math.Abs(sum1 - sum2);
        }
        if (memo[index, sum1] != -1) {
            return memo[index, sum1];
        }
        int diff1 = Helper(stones, index + 1, sum1 + stones[index], sum2, memo);
        int diff2 = Helper(stones, index + 1, sum1, sum2 + stones[index], memo);
        memo[index, sum1] = Math.Min(diff1, diff2);
        return memo[index, sum1];
    }

    public int LastStoneWeightII(int[] stones) {
        int totalSum = 0;
        foreach (var stone in stones) totalSum += stone;
        var memo = new int[stones.Length, totalSum + 1];
        for (int i = 0; i < stones.Length; ++i) {
            for (int j = 0; j <= totalSum; ++j) {
                memo[i, j] = -1;
            }
        }
        return Helper(stones, 0, 0, 0, memo);
    }
}

The Python implementation leverages backtracking with memoization to explore all potential partitions of the stones. By storing computed differences in the memo table, the function minimizes redundant evaluations of the same state, which results in efficient discovery of the minimal stone weight difference.

Complexity

Time Complexity: O(n * total_sum)
Space Complexity: O(n * total_sum)

Try this approach in the editor

Approach 3: Default Approach

func lastStoneWeightII(stones []int) int {
	s := 0
	for _, v := range stones {
		s += v
	}
	m, n := len(stones), s>>1
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			dp[i][j] = dp[i-1][j]
			if stones[i-1] <= j {
				dp[i][j] = max(dp[i][j], dp[i-1][j-stones[i-1]]+stones[i-1])
			}
		}
	}
	return s - dp[m][n]*2
}
impl Solution {
    #[allow(dead_code)]
    pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
        let n = stones.len();
        let mut sum = 0;

        for e in &stones {
            sum += *e;
        }

        let m = (sum / 2) as usize;
        let mut dp: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];

        // Begin the actual dp process
        for i in 1..=n {
            for j in 1..=m {
                dp[i][j] = if stones[i - 1] > (j as i32) {
                    dp[i - 1][j]
                } else {
                    std::cmp::max(
                        dp[i - 1][j],
                        dp[i - 1][j - (stones[i - 1] as usize)] + stones[i - 1],
                    )
                };
            }
        }

        sum - 2 * dp[n][m]
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n * sum/2)
Space Complexity: O(sum/2)

Backtracking with Memoization Approach

Time Complexity: O(n * total_sum)
Space Complexity: O(n * total_sum)

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Backtracking with MemoizationO(n * sum)O(n * sum)Useful for explaining recursion and overlapping subproblems before converting to DP
Dynamic Programming (Subset Sum / Knapsack)O(n * sum)O(sum)Best practical solution; efficient when total stone weight is reasonably bounded

Frequently asked questions

Is Last Stone Weight II easy or hard?

Last Stone Weight II is generally classified as a medium difficulty problem. The main challenge is recognizing that the stone-smashing process reduces to a partition problem and applying a knapsack-style dynamic programming solution.

How to solve Last Stone Weight II in O(n)?

A strict O(n) solution is not possible because the problem depends on achievable subset sums up to half of the total weight. The most efficient approach is O(n * sum) using dynamic programming. It iteratively builds reachable subset sums and selects the one closest to total/2.

What is the best approach for Last Stone Weight II?

The best approach uses dynamic programming with a subset-sum (0/1 knapsack) formulation. Instead of simulating stone smashing, partition the stones into two groups with sums as close as possible. Compute the largest achievable subset sum not exceeding half of the total weight. The final result becomes total - 2 * bestSubsetSum, with time complexity O(n * sum).

What data structure is used in Last Stone Weight II?

The optimal solution primarily uses a dynamic programming array (often a boolean or integer array) to track reachable subset sums. The input itself is processed as an array of integers, and the DP structure enables efficient state transitions similar to the 0/1 knapsack problem.

What is the time complexity of Last Stone Weight II?

The optimal dynamic programming solution runs in O(n * sum) time, where n is the number of stones and sum is the total weight of all stones. Space complexity can be reduced to O(sum) using a 1D DP array. Recursive backtracking without memoization would take O(2^n) time.

Last Stone Weight II Python or Java solution approach?

Both Python and Java implementations typically use the same subset-sum dynamic programming idea. Create a DP array of size total/2 + 1, iterate through each stone, and update reachable sums in reverse order. After processing all stones, find the largest achievable sum near half of the total weight.

Is Last Stone Weight II asked at Google, Amazon, or Meta?

This problem represents a classic partition and knapsack-style dynamic programming pattern commonly asked in technical interviews. Variations of subset partition problems frequently appear at companies like Amazon, Google, and Meta because they test DP state design and optimization skills.

Comments

Next problem · similarPartition Array Into Two Arrays to Minimize Sum DifferenceHard
Now write it yourselfClose this page and solve Last Stone Weight II in the editor, without looking.
Practise Last Stone Weight II