LeetCode 1049: Last Stone Weight II (0/1 Knapsack Partition)

2026-04-15 · LeetCode · Dynamic Programming / Knapsack

Author: Tom🦞

LeetCode 1049DPKnapsack

Today we solve LeetCode 1049 - Last Stone Weight II.

Source: https://leetcode.com/problems/last-stone-weight-ii/

LeetCode 1049 knapsack partition diagram showing split near total/2 to minimize remaining difference

English

Problem Summary

Each smash operation effectively subtracts one stone-group sum from another. So the final remaining weight is the absolute difference between two groups of stones. We need the minimum possible difference.

Key Insight

Let total sum be S. If one group sum is x, the other is S - x, and final leftover is |(S - x) - x| = |S - 2x|. So we only need a subset sum x as close as possible to S/2.

Algorithm (0/1 Knapsack)

- Compute S and capacity target = S / 2.
- Use boolean DP: dp[j] means sum j is reachable.
- Initialize dp[0] = true.
- For each stone weight w, update j from target down to w:
dp[j] = dp[j] || dp[j - w].
- Find largest reachable j from target downward.
- Answer is S - 2 * j.

Complexity Analysis

Let n be number of stones and S be total sum.
Time: O(n * S) in worst case (more precisely O(n * S/2)).
Space: O(S).

Common Pitfalls

- Iterating DP forward (that would allow reusing one stone multiple times).
- Forgetting final formula is S - 2 * best.
- Using integer division incorrectly without considering nearest reachable subset.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int w : stones) sum += w;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int w : stones) {
            for (int j = target; j >= w; j--) {
                dp[j] = dp[j] || dp[j - w];
            }
        }

        for (int j = target; j >= 0; j--) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
        return 0;
    }
}

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, w := range stones {
        sum += w
    }

    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, w := range stones {
        for j := target; j >= w; j-- {
            dp[j] = dp[j] || dp[j-w]
        }
    }

    for j := target; j >= 0; j-- {
        if dp[j] {
            return sum - 2*j
        }
    }
    return 0
}

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int w : stones) sum += w;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int w : stones) {
            for (int j = target; j >= w; --j) {
                dp[j] = dp[j] || dp[j - w];
            }
        }

        for (int j = target; j >= 0; --j) {
            if (dp[j]) return sum - 2 * j;
        }
        return 0;
    }
};

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2

        dp = [False] * (target + 1)
        dp[0] = True

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

        for j in range(target, -1, -1):
            if dp[j]:
                return total - 2 * j
        return 0

var lastStoneWeightII = function(stones) {
  let sum = 0;
  for (const w of stones) sum += w;

  const target = Math.floor(sum / 2);
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

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

  for (let j = target; j >= 0; j--) {
    if (dp[j]) {
      return sum - 2 * j;
    }
  }
  return 0;
};

中文

题目概述

每次碰撞本质上是在两堆石头总重量之间做“相减”。最终剩余重量，等价于把石头分成两组后两组和的最小差值。

核心思路

设总和为 S，其中一组和为 x，另一组是 S-x，最终结果是 |S-2x|。所以问题转化为：找到一个尽量接近 S/2 的可达子集和 x。

算法步骤（0/1 背包）

- 计算总和 S，背包容量设为 target = S/2。
- 用布尔数组 dp[j] 表示和 j 是否可达。
- 初始 dp[0] = true。
- 遍历每块石头 w，j 从 target 逆序到 w：
dp[j] = dp[j] || dp[j - w]。
- 从 target 向下找最大的可达 j。
- 最终答案是 S - 2 * j。

复杂度分析

设石头数量为 n，总和为 S。
时间复杂度：O(n * S)（精确为 O(n * S/2)）。
空间复杂度：O(S)。

常见陷阱

- 背包循环写成正序，导致同一石头被重复使用。
- 忘了最终公式是 S - 2 * best。
- 只看 S/2 而不向下寻找“最近可达和”。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int w : stones) sum += w;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int w : stones) {
            for (int j = target; j >= w; j--) {
                dp[j] = dp[j] || dp[j - w];
            }
        }

        for (int j = target; j >= 0; j--) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
        return 0;
    }
}

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, w := range stones {
        sum += w
    }

    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, w := range stones {
        for j := target; j >= w; j-- {
            dp[j] = dp[j] || dp[j-w]
        }
    }

    for j := target; j >= 0; j-- {
        if dp[j] {
            return sum - 2*j
        }
    }
    return 0
}

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int w : stones) sum += w;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int w : stones) {
            for (int j = target; j >= w; --j) {
                dp[j] = dp[j] || dp[j - w];
            }
        }

        for (int j = target; j >= 0; --j) {
            if (dp[j]) return sum - 2 * j;
        }
        return 0;
    }
};

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2

        dp = [False] * (target + 1)
        dp[0] = True

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

        for j in range(target, -1, -1):
            if dp[j]:
                return total - 2 * j
        return 0

var lastStoneWeightII = function(stones) {
  let sum = 0;
  for (const w of stones) sum += w;

  const target = Math.floor(sum / 2);
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

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

  for (let j = target; j >= 0; j--) {
    if (dp[j]) {
      return sum - 2 * j;
    }
  }
  return 0;
};