Problem statement

https://leetcode.com/problems/closest-subsequence-sum/

Solution

The idea is to separate array into two almost equal parts and generate all possible sums of subsequences for both of them and then use 2sum (closest) problem: we can sort data and use two pointers approach.

Complexity

Time complexity is O(2^(n/2) * n) for sorting part and O(2^(n/2)) for the rest. So, total complexity is O(2^(n/2)), space complexity as well.

Code

class Solution:
    def minAbsDifference(self, nums, goal):
        def sums(arr):
            ans = {0}
            for el in arr:
                ans = {i + el for i in ans} | ans | {el}
            return sorted(ans)
        
        n = len(nums)
        lft, rgh = sums(nums[:n//2]), sums(nums[n//2:])
        beg, end, ans = 0, len(rgh) - 1, inf
        
        while beg < len(lft) and end >= 0:
            sm = lft[beg] + rgh[end]
            ans = min(ans, abs(sm - goal))

            if sm <= goal:
                beg += 1
            elif sm > goal:
                end -= 1
                
        return ans