class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        nums.sort(key=lambda x: -abs(x))
        neg = [0 for _ in range(n+1)]
        pos = [0 for _ in range(n+1)]
        for i in range(n-1, -1, -1):
            if nums[i] < 0:
                neg[i] = neg[i+1] + nums[i]
                pos[i] = pos[i+1]
            else:
                pos[i] = pos[i+1] + nums[i]
                neg[i] = neg[i+1]
        # print(nums, pos, neg)
        ans = abs(goal)
        s = set([0])
        def check(a, b):
            if b < goal - ans or goal + ans < a:
                return False
            return True
        for i in range(n):
            s = set([x for x in s if check(x+neg[i], x+pos[i])])
            # print(s)
            t = set()
            for x in s:
                y = x + nums[i]
                if abs(y - goal) < ans:
                    ans = abs(y - goal)
                t.add(y)
            s |= t
        return ans
                
                
            

Create lc1755.py