Leetcode 1130 Solution

This article provides solution to leetcode question 1130 (last-stone-weight-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 1130" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        self.total = sum(stones)
        self.ans = 0

        stones.sort()

        def dfs(stones, i, cur, target):
            if self.ans == target:
                return
            elif cur > target:
                return
            elif cur > self.ans:
                self.ans = cur

            for j in range(i, len(stones)):
                if i != j and stones[j] == stones[j - 1]:
                    continue

                dfs(stones, j + 1, cur + stones[j], target)

        dfs(stones, 0, 0, self.total // 2)

        return self.total - 2 * self.ans