1755. Closest Subsequence Sum (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums) // 2
        nums1, nums2 = nums[ : n], nums[n : ]
        s1, s2 = {0}, {0}
        for num in nums1:
            s1 |= {x + num for x in s1}
        for num in nums2:
            s2 |= {x + num for x in s2}
        s1 = sorted(s1)
        result = inf
        for num in s2:
            i = bisect_left(s1, goal - num)
            result = min(result, abs(s1[min(i, len(s1) - 1)] + num - goal), abs(s1[i - 1] + num - goal))
        return result