What is the brute force approach and complexity for Last Stone Weight II?

Give every stone a + or − sign; the last weight is the smallest |signed sum| with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Last Stone Weight II?

Find the largest subset sum ≤ total / 2 with one row; the answer is total − 2s with optimal time complexity O(N · S) and space complexity O(S).

How do you identify the pattern for Last Stone Weight II?

Look for key signals in the prompt: "smash two stones: the result is their difference" indicates Each smash is a + and a − sign on two stones. The last stone is a signed sum of the original weights.; "smallest possible weight of the last stone" indicates The smallest |signed sum| is the smallest difference between two groups → Minimum Subset Sum Difference.; "the order of the smashes" indicates The order is free, because the best sign pattern can always be reached. Only the signs matter..

Last Stone Weight II

Medium·LeetCode #1049 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You have a pile of stones, and each stone has a weight. In one turn, pick any two stones and smash them together:

If they weigh the same, both stones are gone.
If one weighs x and the other weighs y, with x < y, the lighter stone is gone and the heavier one now weighs y − x.

Keep smashing until at most one stone is left. Return the smallest weight the last stone can have. If no stone is left, return 0.

Input

An array stones, where stones[i] is the weight of stone i.

Output

The smallest weight the last stone can have, or 0 if no stone is left. The function is int lastStoneWeightII(vector<int>& stones).

Example 1

Input: stones = [2, 7, 4, 1, 8, 1]

Output: 1

Smash 4 with 2 (left 2), then 8 with 7 (left 1), then 2 with 1 (left 1). Two 1s are left, and they cancel. The last stone weighs 1, and no order does better.

Example 2

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

Output: 5

Put 40 and 33 in one group (sum 73) and 31, 26 and 21 in the other (sum 78). The gap between the groups is 5, and that is the best the last stone can do.

Constraints

• 1 ≤ stones.length ≤ 30
• 1 ≤ stones[i] ≤ 100

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“smash two stones: the result is their difference”

→ Each smash is a + and a − sign on two stones. The last stone is a signed sum of the original weights.

“smallest possible weight of the last stone”

→ The smallest |signed sum| is the smallest difference between two groups → Minimum Subset Sum Difference.

“the order of the smashes”

→ The order is free, because the best sign pattern can always be reached. Only the signs matter.

Approach Complexity Ladder

Brute Force — try a + or − sign on every stoneO(2^N)O(N)

Give every stone a + or − sign; the last weight is the smallest |signed sum|

Optimal — 1D bool row over half the totalO(N · S)O(S)

Find the largest subset sum ≤ total / 2 with one row; the answer is total − 2s

Brute Force Intuition

Each smash replaces two stones by their difference, so every stone left is a signed sum of the original stones. Try all 2^N sign patterns, take the absolute value of each sum, and keep the smallest. The order of the smashes never needs checking, because the best sign pattern can always be reached.

Recognition rule for this sub-pattern:

Two equal/close groups ⇔ find a subset with sum near total/2.

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture