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
time, space.