Closest Subsequence sum

"""
Find the minimum absolute difference between the sum of any subsequence
of `nums` and the given `goal`.

----------------------------
🧠 Intuition (Meet-in-the-Middle)
----------------------------
A brute force approach would generate all subset sums, which takes O(2^n),
and is infeasible for n up to 40.

To optimize, we use the Meet-in-the-Middle (MITM) technique:

1. Split the array into two halves:
    - left half (L)
    - right half (R)

2. Generate all possible subset sums for both halves:
    - left_sums  → all subset sums of L
    - right_sums → all subset sums of R

    Each half has at most 2^(n/2) ≈ 2^20 elements, which is manageable.

3. Reformulate the problem:
    Instead of directly finding a subset sum close to `goal`,
    we try to combine:
        left_sum + right_sum ≈ goal

    For a fixed left_sum (l), we want:
        right_sum ≈ (goal - l)

    This transforms the problem into a search problem.

4. Optimization using Binary Search:
    - Sort the list of right_sums
    - For each left_sum:
        - Compute target = goal - left_sum
        - Use binary search to find the closest value in right_sums
        - Check both the insertion point and its previous index

----------------------------
⚙️ Algorithm Steps
----------------------------
- Generate subset sums for both halves
- Sort one half (right_sums)
- Iterate over left_sums:
    - Use binary search to find closest complement
    - Update minimum absolute difference

----------------------------
⏱ Time Complexity
----------------------------
- Generating subset sums: O(2^(n/2))
- Sorting: O(2^(n/2) log(2^(n/2)))
- Binary search for each element: O(2^(n/2) log(2^(n/2)))

Overall: O(n * 2^(n/2))

----------------------------
📦 Space Complexity
----------------------------
- O(2^(n/2)) for storing subset sums

----------------------------
🎯 Key Insight
----------------------------
Even though the problem does not provide a fixed target sum,
we dynamically create a target:
    target = goal - left_sum

This enables us to apply Meet-in-the-Middle efficiently.
"""
from bisect import bisect_left, bisect_right
from math import inf
def subsets_sum(arr):
    ans=[0]
    for i in arr:
        subset_sums=[]
        for subset in ans:
            subset_sums.append(i+subset)
        ans+=subset_sums
    return ans
class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n=len(nums)//2
        arr1=subsets_sum(nums[:n])
        arr2=subsets_sum(nums[n:])

        arr2.sort()
        ans=inf
        for i in arr1:
            target=goal-i
            first_idx=bisect_left(arr2,target)
            if first_idx<len(arr2):
                ans=min(ans, abs(i+arr2[first_idx]-goal))
            if first_idx>0:
                ans=min(ans, abs(i+arr2[first_idx-1]-goal))
        return abs(ans)