Problem 1049

Abstract / Summary

Split the stones into two groups to make their total weights as close as possible and find the difference.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1049.py

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        result = +inf

        # partition stones into two groups
        # which have (almost) the same weight
        # the weight difference is the final result

        stones.sort(reverse = True) # search should abort earlier
        total  = sum(stones)
        size   = len(stones)

        @cache
        def deeper(pos, weight):
            if pos == size:
                return

            nonlocal result
            if result == 0: # already found perfect match
                return

            # weight difference
            other  = total - weight
            diff   = abs(weight - other)
            result = min(result, diff)

            # keep going
            if weight < other:
                deeper(pos + 1, weight)               # push current stone to other group
                deeper(pos + 1, weight + stones[pos]) # include stone in our group

        deeper(0, 0)
        return result
33 lines | 1030 bytes | submitted May 10, 2024 | GitHub   42% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 59% (200k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Dynamic Programming
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the “last stone weight II” problem by treating it as a partition problem: the stones are divided into two groups whose total weights are as close as possible. The absolute difference between the two group sums is the minimal possible final stone weight. The algorithm explores subsets of stones using a depth-first recursion with memoization, while maintaining a global best difference that can prune further exploration once a perfect balance (difference = 0) is found.

Key Steps

Sorting and Pre-computation

stones.sort(reverse=True)          # larger stones first
total = sum(stones)                # sum of all stones
size = len(stones)                 # number of stones

Sorting in descending order allows the recursion to encounter large weight contributions early, which can lead to an early reduction of the global result and therefore earlier termination of branches that cannot improve the current best.

Recursive Exploration with Caching

@cache
def deeper(pos, weight):
    if pos == size:
        return

    nonlocal result
    if result == 0:
        return

    other = total - weight
    diff = abs(weight - other)
    result = min(result, diff)

    if weight < other:
        deeper(pos + 1, weight)               # stone goes to the opposite group
        deeper(pos + 1, weight + stones[pos]) # stone added to the current group

The function deeper receives the current index pos and the accumulated weight of the first group (weight). The base case stops when all stones have been considered. The nonlocal result variable holds the best difference seen so far.

At each call the algorithm computes the weight of the complementary group (other) and updates result with the smaller of the existing best and the newly computed difference.

The conditional if weight < other: ensures that the recursion only proceeds when the first group is not already heavier than the second. This prevents symmetric exploration of mirrored partitions, effectively halving the search space.

The @cache decorator memoizes calls based on (pos, weight). When the same state is reached through different paths, the cached result avoids redundant work, turning the exponential subset enumeration into a tractable dynamic programming process.

Initiation and Return

deeper(0, 0)
return result

The recursion starts with an empty first group (weight = 0) at the first stone (pos = 0). After the search finishes, result contains the minimal achievable weight difference, which is returned as the answer.

Edge Cases Handled

When the input list is empty, size becomes zero, the recursive function immediately returns without altering result. Since result is initialized to positive infinity, the final return would be infinity, which matches the expectation that no stones imply no weight difference.

If all stones have the same weight, the sorting step does not change the order, but the recursion quickly discovers a perfect partition because the cumulative weight can reach exactly half of total. The early-exit condition if result == 0: stops further recursion as soon as this perfect balance is found.

When a single stone is present, the recursion evaluates two possibilities: placing the stone in the first group or leaving it in the second. The computed diff becomes the stone’s weight, which is correctly returned as the minimal possible final weight.

The condition if weight < other: also gracefully handles cases where the first group becomes heavier early; the branch that would further increase the imbalance is omitted, preventing unnecessary exploration of states that cannot improve the current best.

Performance Optimizations

The descending sort pushes larger stones to the front, causing the weight variable to increase rapidly in early recursion levels. This tends to produce larger differences early, which are then reduced as the algorithm explores alternative placements. The early reduction of result enables the if result == 0: shortcut to terminate the entire search as soon as a perfect partition is identified.

Memoization via @cache eliminates repeated work for identical (pos, weight) pairs. Because the recursion only proceeds when weight < other, many symmetric states are never generated, effectively cutting the state space roughly in half.

The combination of these techniques yields a solution that, while conceptually exponential, runs efficiently for typical input sizes encountered in practice, often completing in a fraction of a second for lists of up to thirty stones.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a big pile of heavy stones and you want to put them into two groups. You want both piles to be as close in weight as possible so that they balance out.

The code starts by lining the stones up from the heaviest to the lightest. By doing this, it can make decisions faster. It looks at the total weight of all the stones together and then starts picking stones one by one. For every stone it touches, it has two choices. The first choice is to put that stone into the first pile, and the second choice is to put it into the second pile.

As it keeps choosing where to place each stone, it keeps track of how much total weight is in each pile. Every time it finishes sorting all the stones, it checks the difference between the weight of the first pile and the weight of the second pile. It wants that difference to be as small as possible. If it finds a way to make the two piles weigh exactly the same, the difference becomes zero, and it stops searching because it knows it cannot get better than that. It keeps doing this for every possible combination until it finds the smallest difference between the two groups.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.44 | σ = 1.69

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python JS Java Go Rust
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
everthis JS
fsq C++
halfrost Go
JoshCrozier JS
lkwq007 Python
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fsq C++
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
wisdompeak C++
31 links | 17 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

5 solutions   May 10, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality