Write min_abs_difference(nums: list[int], goal: int) -> int. Choose any subset of nums (possibly empty, whose sum is 0) and return the smallest possible value of |sum(subset) - goal|.
With up to 40 numbers there are 2^40 subsets, far too many, and the values are too large for a DP over sums. Aim for about O(2^(n/2) · n).
min_abs_difference([4, -8, 11, 2], 5) # 0 (11 - 8 + 2 = 5)
min_abs_difference([6, 9], 20) # 5 (6 + 9 = 15)
min_abs_difference([3, 7], -4) # 4 (empty subset: |0 - (-4)| = 4)
Constraints: 1 ≤ len(nums) ≤ 40, -10^7 ≤ nums[i] ≤ 10^7, -10^9 ≤ goal ≤ 10^9.
Show hint
Every subset is a subset of the first half plus a subset of the second half, and each half has only about 2^20 subset sums. For each sum a from one half, the best partner is the sum from the other half closest to goal - a; sorting that half makes the partner quick to find.