Lc1755

class Solution:
    def minAbsDifference(self, A: List[int], goal: int) -> int:

        """
         Approach 1:   tc O(N* 2^(N/2))    sc O(2^(N/2))
        1. cut half
        2. find all sums
        3. sort
        4. two sum - closest to target (medium)
        """ 
        n = len(A)
        left  = self.make(A[:n//2])
        print(left)
        right = self.make(A[n//2:])
        
        print(right)
        left.sort()
        
        right.sort(reverse=True)
        
        ans = float('inf')
        i,j = 0,0
        
        # two sum closest to target goal 
        while i < len(left) and j < len(right):
            cur = left[i] + right[j]
            ans = min(ans, abs(goal - cur))
            if cur > goal: 
                j += 1
            elif cur < goal:
                i += 1
            else:
                return 0 
        return ans 
    # combination sum 
    def make(self,arr):
        n = len(arr)
        res = [0] * (1 << n) 
        for i in range(n):
            for mask in range(1 << i):                
                res[mask | (1 << i)] = res[mask] + arr[i]
        return res 
    
    
  

class Solution:
    def minAbsDifference(self, A: List[int], goal: int) -> int:
        """ tc O(2^(N/1))  sc O(2^(N/2))
        1. merge sort to get half arr combination sum in sorted order 
        2. two sum to get the closest diff with goal 
        """
        n = len(A)
        self.left, self.right = [],[]
        self.left = self.get_sum(self.left,A[:n//2])
        self.right = self.get_sum(self.right,A[n//2:])
        #print(self.left,'lt')
        #print(self.right,'rt')
        res = float('inf')
        i,j = 0,len(self.right)-1
        while i < len(self.left) and j >= 0:
            cur = self.left[i]  + self.right[j]
            res = min(res,abs(goal-cur))
            if cur>goal:
                j -= 1
            elif cur < goal:
                i  += 1
            else:
                return 0
            #print(f'i is {i}, j is {j}, res is {res}, goal-cur = {abs(goal-cur)}')   
        return res 
    def get_sum(self,A,B):
        A.append(0)
        for b in B:
            BB = []
            n = len(A)
            # merge sort ????   {b_i} and{b_i} + b
            i=j = 0 
            while i < n or j < n:
                if i == n:
                    BB.append(A[j]+b)
                    j += 1
                elif j == n:
                    BB.append(A[i])
                    i += 1
                elif A[i] < A[j] + b:
                    BB.append(A[i])
                    i += 1
                else:
                    BB.append(A[j]+b)
                    j += 1
            A = BB 
        return A