Closest Subsequence Sum - Meet in the Middle

Split the array into two halves. Generate all $2^{20}$ subset sums for each half.

$1.$ Compute all sums for the first half: $O(2^{n/2})$.

$2.$ Compute all sums for the second half: $O(2^{n/2})$.

$3.$ Sort one list.

$4.$ For each sum $s_1$ in the first list, binary search for $goal - s_1$ in the second list to find the closest match.

Total time: $O(2^{n/2} \cdot n)$.