Domain 2MediumMEDIUM

Last Stone Weight II

Partition stones into two subsets to minimize weight difference using subset sum DP up to half total weight.

Domain: medium•Updated: 2026-09-07
#dynamic programming#boolean array#O(N*S)#O(S)

Problem Breakdown

We are given an array of stone weights and a specific operation rule for smashing two stones together. The goal is to find the smallest possible remaining weight after all operations.

Inputs:

  • stones: A list of integers representing weights (1≤length≤301 \le \text{length} \le 30, 1≤weight≤1001 \le \text{weight} \le 100).

Outputs:

  • An integer representing the smallest possible remaining weight (or 0 if no stones remain).

Implicit Logic & Edge Cases:

  • Partitioning View: Every smash operation effectively subtracts 2x2x from the total sum of weights involved in that specific turn. Ultimately, this problem is equivalent to partitioning the set of stones into two subsets: one subset (AA) where we treat their weight as positive and another (BB) where we treat them as negative (conceptually). The final result will be ∣∑A−∑B∣|\sum A - \sum B|.
  • Minimization: To minimize this difference, ∑A\sum A should be as close to half the total sum of all stones as possible. This transforms the problem into a variation of the Subset Sum Problem or 0/1 Knapsack Problem.
  • Constraints Check: With N≤30N \le 30 and weights ≤100\le 100, the maximum total weight is 30003000. A dynamic programming approach based on sum values is computationally feasible (O(N⋅S)O(N \cdot S)).

Intuition

A brute-force simulation of smashing stones would require tracking every possible state transition. Since we can pick any two stones at each step, there are too many permutations to explore exhaustively (complexity roughly factorial or exponential depending on implementation), leading to Time Limit Exceeded errors for larger inputs in a general context.

The key insight is recognizing that the order of smashing doesn’t change the final algebraic result if we view it as assigning signs (+1+1 or −1-1) to each stone weight initially. If we assign sign si∈{1,−1}s_i \in \{1, -1\} to every stone wiw_i, the final remaining weight is ∣∑(si⋅wi)∣\left| \sum (s_i \cdot w_i) \right|.

Let Total Sum be SS. We want to minimize: Sfinal=∣(Sum of stones with +1)−(Sum of stones with −1)∣S_{final} = | (\text{Sum of stones with } +1) - (\text{Sum of stones with } -1) | Since (Sum+)+(Sum−)=S(\text{Sum}_{+}) + (\text{Sum}_{-}) = S, we can rewrite this as minimizing ∣S−2⋅(Sum+)∣|S - 2 \cdot (\text{Sum}_{+})|.

To minimize the absolute difference, Sum+\text{Sum}_{+} should be as close to S/2S/2 as possible. Thus, the problem reduces to finding a subset of stones whose sum is at most total_sum // 2 and maximizes that value (Knapsack capacity). The remainder will naturally fall into the negative group.

Approach

  1. Calculate Total Sum: Compute the sum of all stone weights (S).
  2. Define Target Capacity: We want to find a subset with maximum weight ≤S//2\le S // 2. Let this target be target.
  3. Dynamic Programming (Subset Sum): Create a boolean DP array where dp[i] indicates if it’s possible to achieve sum i using a subset of the stones processed so far. Initialize dp[0] = True, others False.
  4. Iterate and Update: For each stone weight, update the reachable sums in reverse order (standard 0/1 Knapsack optimization) to ensure we don’t reuse the same item for the current sum calculation within one iteration.
  5. Find Max Subset Sum: After processing all stones, scan dp from target down to 0 to find the largest index that is reachable (True). Let this be k.
  6. Calculate Result: The answer is S−2⋅kS - 2 \cdot k.

Complexity Analysis

  • Time Complexity: O(N⋅S)O(N \cdot S), where NN is the number of stones and SS is the total weight sum. Given constraints (N=30N=30, max value=100), Smax=3000S_{max} = 3000. Operations ≈90,000\approx 90,000, which fits well within time limits (typically ~1 second allows for millions of operations).
  • Space Complexity: O(S)O(S) to store the boolean DP array. With max sum 3000, this is negligible memory usage (~24KB or less depending on implementation details in Python lists vs sets).

Solution

def lastStoneWeightII(stones):
    total_sum = sum(stones)
    
    # We want to find a subset with maximum weight <= total_sum // 2.
    target = total_sum // 2
    
    # dp[i] will be True if weight i can be achieved by some subset of stones
    reachable_sums = [False] * (target + 1)
    reachable_sums[0] = True
    
    for stone in stones:
        # Iterate backwards to avoid using the same item multiple times 
        # within a single iteration (standard 0/1 Knapsack space optimization).
        # We only care about sums up to 'target'.
        if stone > target:
            continue
        
        for i in range(target, stone - 1, -1):
            if reachable_sums[i - stone]:
                reachable_sums[i] = True
                
    # Find the largest achievable sum <= target. 
    # Since we filled dp array from bottom-up logic implicitly via iteration,
    # scanning backwards finds the max subset sum closest to half total weight.
    k = 0
    for i in range(target, -1, -1):
        if reachable_sums[i]:
            k = i
            break
            
    return total_sum - 2 * k

# Example usage:
print(lastStoneWeightII([2,7,4,1,8,1])) # Output: 1

Edge Cases Handled

  • Single Stone: If stones has length 1 (e.g., [5]), total sum is 5. Target is 2. DP array size 3 ([T,F,F]). Loop runs for stone 5, range(2,4) empty due to bounds check or logic flow where loop doesn’t execute if start < stop with negative step (handled by if stone > target: continue optimization added). Max subset found is 0. Result 5−0=55 - 0 = 5. Correct (cannot smash).
  • All Stones Equal: If stones are [1, 1], total sum 2, target 1. DP finds reachable {0, 1}. Max subset sum 1. Result 2−2(1)=02 - 2(1) = 0. Correct.
  • Odd Total Sum: The integer division // 2 handles the remainder naturally; the difference between partition sums will be at least 1 if total is odd (e.g., [3,4], target=3, reachable {0,3}, result 7−6=17 - 6 = 1).
  • **Large We