Closest Subsequence Sum

hard meet in the middle binary search bitmask

Problem

Given an integer array nums and an integer goal, choose any subsequence (remove some, all, or none of the elements). If the chosen elements sum to sum, minimize abs(sum − goal). Return that minimum possible value.

With up to 40 elements, brute force over all 2⁴⁰ subsequences is too slow, so we split the array in half and combine the two sides. The empty subsequence (sum 0) is always allowed.

Inputnums = [5, -7, 3, 5], goal = 6

Output0

Taking the whole array sums to 5 − 7 + 3 + 5 = 6, exactly the goal, so abs(6 − 6) = 0.

nums (comma-separated)

goal

def minAbsDifference(nums, goal):
    n = len(nums)
    half = n // 2

    def subset_sums(arr):                 # all 2^len(arr) subset sums
        sums = [0]
        for v in arr:
            sums += [s + v for s in sums]
        return sums

    A = subset_sums(nums[:half])          # left half
    B = sorted(subset_sums(nums[half:]))  # right half, sorted

    best = abs(goal)                      # empty subsequence (sum 0)
    for a in A:
        need = goal - a                   # want B value near this
        lo, hi = 0, len(B)                # binary search lower bound
        while lo < hi:
            mid = (lo + hi) // 2
            if B[mid] < need:
                lo = mid + 1
            else:
                hi = mid
        if lo < len(B):                   # closest at or above need
            best = min(best, abs(a + B[lo] - goal))
        if lo > 0:                        # closest just below need
            best = min(best, abs(a + B[lo - 1] - goal))
    return best

function minAbsDifference(nums, goal) {
  const n = nums.length, half = n >> 1;

  function subsetSums(arr) {                 // all 2^len subset sums
    let sums = [0];
    for (const v of arr) sums = sums.concat(sums.map(s => s + v));
    return sums;
  }

  const A = subsetSums(nums.slice(0, half)); // left half
  const B = subsetSums(nums.slice(half)).sort((p, q) => p - q);

  let best = Math.abs(goal);                 // empty subsequence (sum 0)
  for (const a of A) {
    const need = goal - a;                   // want B value near this
    let lo = 0, hi = B.length;               // binary search lower bound
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (B[mid] < need) lo = mid + 1;
      else hi = mid;
    }
    if (lo < B.length)                        // closest at or above need
      best = Math.min(best, Math.abs(a + B[lo] - goal));
    if (lo > 0)                               // closest just below need
      best = Math.min(best, Math.abs(a + B[lo - 1] - goal));
  }
  return best;
}

int minAbsDifference(int[] nums, int goal) {
    int n = nums.length, half = n / 2;
    long[] A = subsetSums(nums, 0, half);        // left half
    long[] B = subsetSums(nums, half, n);        // right half
    Arrays.sort(B);                              // sort for binary search

    long best = Math.abs((long) goal);           // empty subsequence
    for (long a : A) {
        long need = goal - a;                    // want B value near this
        int lo = 0, hi = B.length;               // binary search lower bound
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (B[mid] < need) lo = mid + 1;
            else hi = mid;
        }
        if (lo < B.length)                        // closest at or above need
            best = Math.min(best, Math.abs(a + B[lo] - goal));
        if (lo > 0)                               // closest just below need
            best = Math.min(best, Math.abs(a + B[lo - 1] - goal));
    }
    return (int) best;
}

int minAbsDifference(vector<int>& nums, int goal) {
    int n = nums.size(), half = n / 2;
    vector<long> A = subsetSums(nums, 0, half);   // left half
    vector<long> B = subsetSums(nums, half, n);   // right half
    sort(B.begin(), B.end());                    // sort for binary search

    long best = abs((long) goal);                // empty subsequence
    for (long a : A) {
        long need = goal - a;                    // want B value near this
        int lo = lower_bound(B.begin(), B.end(), need) - B.begin();
        if (lo < (int) B.size())                  // closest at or above need
            best = min(best, abs(a + B[lo] - goal));
        if (lo > 0)                               // closest just below need
            best = min(best, abs(a + B[lo - 1] - goal));
    }
    return (int) best;
}

Explanation

Trying every subsequence is 2ⁿ, which blows up at n = 40. The trick is meet in the middle: split nums into two halves of about 20 elements each. Each half has only 2²⁰ subsets, which is manageable.

We enumerate every subset sum of the left half into a list A and every subset sum of the right half into a list B. Any subsequence of the whole array is exactly one choice from the left side plus one from the right, so its total is some a + b with a ∈ A and b ∈ B. We want a + b as close to goal as possible.

The empty subsequence (sum 0) is always valid, so we initialise best = abs(goal) before the search.

Fix one side: for each a in A, the best partner is the b nearest to need = goal − a. If we sort B first, we can find that nearest value with a binary search (the lower_bound position). The closest candidate is either the element at that position or the one just before it, so we check both and update best.

Example: nums = [5, -7, 3, 5], goal = 6. The left half [5, -7] gives sums {0, 5, -7, -2}; the right half [3, 5] gives sorted sums {0, 3, 5, 8}. For a = -2 we need 8, and B contains 8 exactly, so a + b = 6 = goal and the answer is 0.

Time: O(2^n/2 · n) Space: O(2^n/2)