Closest Subsequence Sum - Implementation

Here is the implementation using meet-in-the-middle:

function minAbsDifference(nums, goal):
    n = nums.length
    half = n / 2

    left = generateAllSums(nums[0..half-1])
    right = generateAllSums(nums[half..n-1])

    sort(right)
    result = infinity

    for s1 in left:
        target = goal - s1
        // Binary search for closest to target in right
        idx = lowerBound(right, target)

        if idx < right.length:
            result = min(result, abs(s1 + right[idx] - goal))
        if idx > 0:
            result = min(result, abs(s1 + right[idx-1] - goal))

    return result

function generateAllSums(arr):
    sums = [0]
    for num in arr:
        newSums = []
        for s in sums:
            newSums.append(s + num)
        sums = sums + newSums
    return sums

$O(2^{n/2} \cdot n)$ time, $O(2^{n/2})$ space.