Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Closest Subsequence Sum

Problem (restated)

Pick any subsequence of nums (n ≤ 40) whose sum is as close as possible to goal. Return the minimum absolute difference.

Intuition

2^40 is impossible; 2^20 is about a million. Split, enumerate all subset sums on each half (include 0), sort the left, and for each right sum binary-search goal − right.

Approaches

Meet in the middle, closest subset sum

Unverified

Time O(n·2^{n/2})Space O(2^{n/2})

Idea. Generate 2^{n/2} left sums, sort. For each right sum r, find the left sum closest to goal − r — the largest ≤ need (lo) and lo+1. Empty subsequence is a valid candidate.

Walkthrough. nums=[5,7,−3], goal=6: closest sums 5 or 7 → difference 1. [1,2,3], goal=−7 → empty sum 0, difference 7.

Trade-offs. Hashing left sums only helps exact hits; closest needs a sorted list and both neighbors of the insertion point.

Solution

export function minAbsDifference(nums: number[], goal: number): number {
  const mid = nums.length >> 1;
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const allSums = (arr: number[]): number[] => {
    const sums = [0];
    for (const v of arr) {
      const n = sums.length;
      for (let i = 0; i < n; i++) sums.push(sums[i]! + v);
    }
    return sums;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const leftSums = allSums(left).sort((a, b) => a - b);
  let ans = Math.abs(goal);
  for (const r of allSums(right)) {
    const ls = closest(leftSums, goal - r);
    const diff = Math.abs(ls + r - goal);
    if (diff < ans) ans = diff;
  }
  return ans;
}

export function minAbsDifference(nums: number[], goal: number): number {
  const mid = nums.length >> 1;
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const allSums = (arr: number[]): number[] => {
    const sums = [0];
    for (const v of arr) {
      const n = sums.length;
      for (let i = 0; i < n; i++) sums.push(sums[i]! + v);
    }
    return sums;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const leftSums = allSums(left).sort((a, b) => a - b);
  let ans = Math.abs(goal);
  for (const r of allSums(right)) {
    const ls = closest(leftSums, goal - r);
    const diff = Math.abs(ls + r - goal);
    if (diff < ans) ans = diff;
  }
  return ans;
}

Template connection

Canonical closest-subset-sum MITM — the pattern template, with an explicit lo / lo+1 closest check.

Reflection

Split the array in half. Sort each half’s subset sums. For a sum on one side, take the other side’s sum closest to goal - that sum.
The empty subset is 0. If goal is in the array, the difference is 0. Negative sums do not break a sorted search.
The answer is an absolute difference. n is about 40, so each half is 2**(n / 2) sums. One element answers |a - goal|.