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