Problem Link

Solution 1: DFS

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        memo = dict()
        return self.helper(stones, 0, 0, 0, memo)

    def helper(self, stones, i, S1, S2, memo) -> int:
        if (i, S1, S2) in memo:
            return memo[(i, S1, S2)]
        if i == len(stones):
            return abs(S1 - S2)
        res = min(self.helper(stones, i+1, S1 + stones[i], S2, memo), self.helper(stones, i+1, S1, S2 + stones[i], memo))
        memo[(i, S1, S2)] = res
        return res

Solution 2: Dynamic Programming

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        S = sum(stones)
        dp = [False] * (S // 2 + 1)
        L = len(dp)
        dp[0] = True
        for s in stones:
            for i in range(L-1, 0, -1):
                if i >= s:
                    dp[i] = dp[i] or dp[i-s]
        for i in range(L-1, -1, -1):
            if dp[i]:
                return S - i*2