1755. Closest Subsequence Sum - cocoder39/coco39_LC GitHub Wiki

time complexity to construct sum for all subsequences is O(2^n). Idea is to use divide-and-conquer to improve the speed. step 1: slit to 2 halves T = O(2^(n/2)) step 2: iterate one half and try to find the matching pair in the other half so that sum of the 2 is close to goal T = (log(2^(n/2)) * (2^(n/2)))

T = 2O(2^(n/2)) + O(log(2^(n/2)) * (2^(n/2))) = O(n2^(n/2)) is smaller than O(2^n)

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        mid = n//2
        left, right = set(), set()
        self.getSubsequenceSum(nums, mid, 0, 0, left)
        self.getSubsequenceSum(nums, n, mid, 0, right)
        left = sorted(list(left))
        
        diff = float("inf")
        for s in right:
            remain = goal - s
            index = bisect.bisect_left(left, remain)
            if index < len(left):
                diff = min(diff, abs(remain - left[index]))
            if index > 0:
                diff = min(diff, abs(remain - left[index-1]))
        
        return diff
    
    # sums contains all subsequence sums built by subarray of nums ending with end_idx
    def getSubsequenceSum(self, nums, end_idx, cur_idx, total, sums):
        sums.add(total)
        
        if cur_idx >= end_idx:
            return
        
        self.getSubsequenceSum(nums, end_idx, cur_idx+1, total, sums)
        self.getSubsequenceSum(nums, end_idx, cur_idx+1, total+nums[cur_idx], sums)