Problem

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Examples

Example 1

1
2
3
4
5
6
7

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2

1
2

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

Constraints

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

Solution

Method 1 – Subset Sum Dynamic Programming

Intuition

The problem can be transformed into partitioning the stones into two groups such that the difference of their sums is minimized. This is a classic subset sum problem, similar to partitioning an array into two subsets with the minimum difference.

Approach

  1. Compute the total sum of all stones.
  2. Use dynamic programming to find the largest possible sum not exceeding half of the total sum that can be formed by a subset of stones.
  3. The answer is the difference between the total sum and twice this largest possible subset sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int s : stones) {
            for (int j = target; j >= s; --j) {
                dp[j] = dp[j] || dp[j - s];
            }
        }
        for (int j = target; j >= 0; --j) {
            if (dp[j]) return sum - 2 * j;
        }
        return 0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, s := range stones {
        sum += s
    }
    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true
    for _, s := range stones {
        for j := target; j >= s; j-- {
            dp[j] = dp[j] || dp[j-s]
        }
    }
    for j := target; j >= 0; j-- {
        if dp[j] {
            return sum - 2*j
        }
    }
    return 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int s : stones) sum += s;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int s : stones) {
            for (int j = target; j >= s; --j) {
                dp[j] = dp[j] || dp[j - s];
            }
        }
        for (int j = target; j >= 0; --j) {
            if (dp[j]) return sum - 2 * j;
        }
        return 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun lastStoneWeightII(stones: IntArray): Int {
        val sum = stones.sum()
        val target = sum / 2
        val dp = BooleanArray(target + 1)
        dp[0] = true
        for (s in stones) {
            for (j in target downTo s) {
                dp[j] = dp[j] || dp[j - s]
            }
        }
        for (j in target downTo 0) {
            if (dp[j]) return sum - 2 * j
        }
        return 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def lastStoneWeightII(self, stones: list[int]) -> int:
        total = sum(stones)
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for s in stones:
            for j in range(target, s - 1, -1):
                dp[j] = dp[j] or dp[j - s]
        for j in range(target, -1, -1):
            if dp[j]:
                return total - 2 * j
        return 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
        let sum: i32 = stones.iter().sum();
        let target = sum / 2;
        let mut dp = vec![false; (target + 1) as usize];
        dp[0] = true;
        for &s in &stones {
            for j in (s..=target).rev() {
                dp[j as usize] = dp[j as usize] || dp[(j - s) as usize];
            }
        }
        for j in (0..=target).rev() {
            if dp[j as usize] {
                return sum - 2 * j;
            }
        }
        0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    lastStoneWeightII(stones: number[]): number {
        const sum = stones.reduce((a, b) => a + b, 0);
        const target = Math.floor(sum / 2);
        const dp = Array(target + 1).fill(false);
        dp[0] = true;
        for (const s of stones) {
            for (let j = target; j >= s; --j) {
                dp[j] = dp[j] || dp[j - s];
            }
        }
        for (let j = target; j >= 0; --j) {
            if (dp[j]) return sum - 2 * j;
        }
        return 0;
    }
}

Complexity

  • ⏰ Time complexity: O(n * sum/2), where n is the number of stones and sum is the total weight. Each stone and each possible sum up to half the total are considered.
  • 🧺 Space complexity: O(sum/2), for the DP array.