1049. Last Stone Weight II¶
Edited by Charles
Medium · Python · Dynamic Programming
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
Recall 416. Partition Equal Subset Sum for the core idea. The solution in this question partition the list into two subsets with equal values or closest difference.
Original study notes follow, including intermediate snippets and earlier attempts.
Recall 416. Partition Equal Subset Sum for the core idea. The solution in this question partition the list into two subsets with equal values or closest difference.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | February 5, 2026 |
Python solution¶
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
n = len(stones)
total = sum(stones)
target = total // 2
dp = [0] * (target + 1)
for i in range(n):
for j in range(target, stones[i] - 1, -1):
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
return total - 2 * dp[-1]