We have a collection of rocks, each rock has a positive integer weight.
Each turn, we choose any two rocks 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 totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)
 
Example 1:
Input: [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.

 
Note:

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

Difficulty: interview

Starter code:

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        

Solutions:
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        dp = {0}
        total = sum(stones)
        for stone in stones:
            dp |= {_sum + stone for _sum in dp}
        return min(abs(total - _sum - _sum) for _sum in dp)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        res = set()
        res.add(stones[0])
        for n in stones[1:]:
            newres = set()
            for m in res:
                newres.add(n + m)
                newres.add(abs(n - m))
            res = newres
        return min(res)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        def dp(i, j):
            if i==N: return j
            if (i, j) in memo: return memo[(i, j)]
            
            memo[(i, j)] = min(dp(i+1, abs(j+stones[i])), dp(i+1, abs(j-stones[i])))
            return memo[(i, j)]
        
        memo = {}
        N = len(stones)
        return dp(0, 0)

class Solution:
    def lastStoneWeightII(self, arr: List[int]) -> int:
        #0/1 knapsack
        upperBound = sum(arr)//2
        #initialize the dp -> row means use up to ith value, row means the upper bound value 
        dp = [[0 for i in range(upperBound+1)] for j in range(len(arr))]

        #fill in the dp
        #base case when col == 0 -> the upper bound is 0, so the max val is 0 
        for i in range(len(dp)):
            for j in range(len(dp[0])):
                #take i or not
                if(arr[i] <= j):
                    dp[i][j] = max(dp[i-1][j-arr[i]] + arr[i], dp[i-1][j])
                else:
                    dp[i][j] = dp[i-1][j]
        return sum(arr) - 2*dp[-1][-1]

from functools import lru_cache
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        
        n = len(stones)
        if n == 1:
            return stones[0]
        
        @lru_cache(None)
        def dfs(index, curSum):
            if index == n:
                return abs(curSum)
            
            return min(dfs(index + 1, curSum + stones[index]), dfs(index + 1, curSum - stones[index]))
        
        return dfs(0, 0)


import queue
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        return self.topDown(stones, 0, 0, 0, [[None for s in range(total+1)] for i in range(len(stones))])
        
        
    def topDown(self, stones, idx, sum1, sum2, memo):
        
        if idx >= len(stones):
            return abs(sum1-sum2)
        
        if memo[idx][sum1] != None:
            return memo[idx][sum1]
        
        difference_1 = self.topDown(stones, idx+1, sum1+stones[idx], sum2, memo)
        difference_2 = self.topDown(stones, idx+1, sum1, sum2+stones[idx], memo)
        
        memo[idx][sum1] = min(difference_1, difference_2)
        return memo[idx][sum1]

class Solution:
    
    def lastStoneWeightII(self, stones: List[int]) -> int:        
        mem = {} #Mem
        
        def explore(a, b, stones):
            if len(stones) == 0:
                return abs(a-b)
            
            entry = (a, b, len(stones)) #Mem
            if entry in mem:
                return mem[entry]
            
            s = stones.pop()
            m = min(explore(a+s, b, stones), explore(a, b+s, stones))
            stones.append(s)
            
            mem[entry] = m #Mem
            return m
        
        return explore(0, 0, stones)
    
    def lastStoneWeightIITLE(self, stones: List[int]) -> int:
        N = len(stones)
        if not stones:
            return 0
        if N == 1:
            return stones[0]
        if N == 2:
            return abs(stones[0]-stones[1])
        
        out = float('inf')
        for i in range(N):
            for j in range(i+1, N):
                right = stones.pop(j)
                left = stones.pop(i)
                diff = abs(right-left)
                
                out = min(out, self.lastStoneWeightII(stones+[diff]))
                
                stones.insert(i, left)
                stones.insert(j, right)
                
        return out

class Solution:
    
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # find the two groups with the smallest difference
        
        cache = {}
        
        def diffs(s1: int, s2: int, xs: List[int]) -> int:
            if len(xs) == 0:
                return abs(s1 - s2)
            
            if (s1, s2, len(xs)) not in cache:            
                y = xs.pop()
                min_val = min(diffs(s1 + y, s2, xs), diffs(s1, s2 + y, xs))
                xs.append(y)
                cache[(s1, s2, len(xs))] = min_val
                
            return cache[(s1, s2, len(xs))]
            
        return diffs(stones[0], 0, stones[1:])
            
            
            
            
                
            


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2 
        
        dp = [0] * (target + 1)
        
        for stone in stones:
            for i in range(target, stone-1, -1): 
                dp[i] = max(dp[i], dp[i-stone] + stone)
                
        return total - 2*dp[-1]

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        def helper(i, currSum):
            if i == len(stones):
                return abs(total - 2 * currSum)
            if (i, currSum) in cache:
                return cache[(i, currSum)]
            takeIt = helper(i + 1, currSum + stones[i])
            ignoreIt = helper(i + 1, currSum)
            cache[(i, currSum)] = min(takeIt, ignoreIt)
            return cache[(i, currSum)]

        cache = {}
        total = sum(stones)
        return helper(0, 0)



class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        self.dp={}
        def helper(index,total):
            
            if index==len(stones):
                return abs(total)
            
            if (index,total) in self.dp:
                return self.dp[(index,total)]
            
            self.dp[(index,total)]= min(helper(index+1,total+stones[index]),helper(index+1,total-stones[index]))
            return self.dp[(index,total)]
            
            
        return helper(0,0)


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:      
        '''
        Observation: 
        Minimum weight stone is equal to the problem of partionining stones into
        two arrays A and B such that | sum(A) - sum(B) | is minimized.
        
        Idea: Given such a partition, we smash the stones as follows. Choose a in A
        and b in B arbitrarily.
          - if a == b: they both are destroyed
          - if a < b: place b - a into B
          - if a > b: place a - b into A
        Can argue that at the end, the stone remaining will have weight which is
        the difference.
        
        Use a knapsack like DP to solve the problem.
        '''
        
        n = len(stones)
        total = sum(stones)
        # memo keeps track of whether or not we can get a sum of exactly T for
        # the smaller of the two sets (thus, T <= sum(A)/2) using numbers
        # from 0 .. i
        memo = {}
        def dp(i, t):
          if (i,t) in memo:
            return memo[i, t]
          
          if i == -1:
            memo[i, t] = t == 0
          elif t < 0:
            memo[i, t] = False
          else:
            memo[i, t] = dp(i-1, t) or dp(i-1, t - stones[i])
          return memo[i, t]
          
        return min(abs(total - 2*t) for t in range(total//2 + 1) if dp(n-1, t))
        
        


from heapq import heapify,heappush,heappop
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        arr = stones
        n = len(stones)
        su = sum(arr)
        dp = [[0 for i in range(su+1)] for j in range(n+1)]
        for i in range(n + 1): 
            dp[i][0] = 1

        for j in range(1,n+1):
            for i in range(1,su+1):
                dp[j][i] = dp[j-1][i]
                if i-arr[j-1]>=0:
                    dp[j][i] |= dp[j-1][i-arr[j-1]]


        diff = sys.maxsize 

        # Find the largest j such that dp[n][j]  
        # is true where j loops from sum/2 t0 0  
        for j in range(su // 2, -1, -1): 
            if dp[n][j] == True: 
                diff = su - (2 * j) 
                break

        return diff

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        from functools import lru_cache
        
        @lru_cache(None)
        def helper(ind, curr):
            if ind==len(stones):
                return abs(curr)
            
            return min(helper(ind+1, curr+stones[ind]), helper(ind+1, curr-stones[ind]))
        
        return helper(0, 0)


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        mem = {} #Mem
        
        def explore(a, b, stones):
            if len(stones) == 0:
                return abs(a-b)
            
            entry = (a, b, len(stones)) #Mem
            if entry in mem:
                return mem[entry]
            
            s = stones.pop()
            m = min(explore(a+s, b, stones), explore(a, b+s, stones))
            stones.append(s)
            
            mem[entry] = m #Mem
            return m
        
        return explore(0, 0, stones)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        n = len(stones)
        total = sum(stones)
        diff = total
        dp = [[False] * (1 + total) for _ in range(1 + n)]
        for i in range(n + 1):
            dp[i][0] = True
        
        for i in range(1, n + 1):
            s = stones[i - 1]
            for j in range(1, 1 + total):
                if j < s:
                    dp[i][j] = dp[i - 1][j]
                    continue
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - s]
                if dp[i][j]:
                    diff = min(diff, abs(total - 2 * j))
        return diff
        
        
        


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        dp = {0}
        sum_stones = sum(stones)
        
        for stone in stones:
            dp |= {stone + i for i in dp}
            
        return min(abs(sum_stones - i - i) for i in dp)


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # dp = {0}
        # sumA = sum(stones)
        # for a in stones:
        #     dp |= {a + i for i in dp}
        # return min(abs(sumA - i - i) for i in dp)
        dp, sumA = {0}, sum(stones)
        for a in stones:
            dp = {a + x for x in dp} | {a - x for x in dp}
        return min(abs(x) for x in dp)

from functools import lru_cache
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        
        
        lim = len(stones)
        
        
    
        
        @lru_cache(None)
        def r(s,i):
            if i==lim-1:
                return min(s+stones[-1],abs(s-stones[-1]))
            
            else:
                
                
                return min(r(s+stones[i],i+1),r(abs(s-stones[i]),i+1))
                
                
                    
                        
        
        return r(0,0)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        
        target=sum(stones)
        target=target//2
        
        
        dp=[[False]*(target+1) for _ in range(len(stones)+1)]
        
        
        for i in range(len(stones)+1):
            for j in range(target+1):
                
                if j==0:
                    dp[i][j]=True
                    
                elif stones[i-1]<=j:
                    dp[i][j]=dp[i-1][j-stones[i-1]] or dp[i-1][j]
                    
                else:
                    dp[i][j]=dp[i-1][j]
                
                
        for j in reversed(range(target+1)):
            
            if dp[-1][j]:
                return sum(stones)-2*j

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        '''
        DP
        O(N * SUM//2)
        
        As this problem is equal to min diff between dividing arr into two groups, sse dp to store sum//2 and see if we can reach it
        '''
        
        total = sum(stones)
        
        dp = [[None for _ in range(((total // 2) + 1))] for _ in range(len(stones))]
        
        for num in range((total//2)+1):
            if stones[0] <= num:
                dp[0][num] = stones[0]
            else:
                dp[0][num] = 0
        
        
        for index in range(1,len(stones)):
            for num in range((total//2)+1):                
                if stones[index] <= num:
                    take = stones[index] + dp[index - 1][num - stones[index]]
                    dp[index][num] = max(take, dp[index-1][num])
                else:
                    dp[index][num] = dp[index - 1][num]
        
        #print(dp)
        
        return total - dp[-1][-1] - dp[-1][-1]