Closest Subsequence Sum

Problem in Plain English

Find the smallest absolute difference between a subsequence sum and a target. Split up to forty values, enumerate half sums and search sorted complements.

Problem Statement

Given nums and goal, choose any subsequence, including the empty subsequence, and return the minimum abs(sum-goal). The official exercise allows negative numbers, so a sum that currently exceeds goal cannot safely be pruned. Only the distance is required; different subsequences with the same sum are equivalent answers.

Constraints

1 <= nums.length <= 40.
-10^7 <= nums[i] <= 10^7.
-10^9 <= goal <= 10^9.
The empty subsequence is allowed.

Examples

Example 1

Input: nums = [5,-7,3,5], goal = 6
Output: 0

Taking all four values yields 6. Its left sum -2 and right sum 8 give zero distance.

Example 2

Input: nums = [7,-9,15,-2], goal = -5
Output: 1

The subset [7,-9,-2] sums to -4, distance one. Enumerating all half pairs shows that no sum equals -5.

Example 3

Input: nums = [1,2,3], goal = -7
Output: 7

Every nonempty sum is positive. The empty subset sums to zero and is the closest.

Example 4

Input: nums = [0,0], goal = 1
Output: 1

All four subsets sum to zero. Duplicate sums do not change the minimum distance.

Intuition

Forty elements have over a trillion subsets, but twenty have about a million. Divide the array into two halves. Every full subset consists of one subset from each half, so enumerate each half separately and look for pairs whose sums approach goal. In Example 1 the halves [5,-7] and [3,5] produce sums [0,5,-7,-2] and [0,3,5,8]. Left sum -2 pairs with right sum 8 to reach goal 6 exactly. Including zero in both lists represents the empty subset and subsets confined to one half.

Approaches

Meet in the Middle

Optimal

Solution Details

Reveal Meet in the Middle: intuition, complexity, and code

Intuition

Enumerate each half’s sums by starting with [0] and appending oldSum+value for every previously existing sum. Freeze the old list size before appending so each value is used at most once. Sort the right sums numerically. For each left sum x, binary-search the first right sum at least goal-x; compare it and its predecessor. Duplicates may remain because only the closest value matters. Initialize the answer with abs(goal), explicitly allowing the empty subset. This cuts the exponential enumeration from 2^n to two lists of about 2^(n/2).

Step-by-Step Logic

Split into [5,-7] and [3,5]; initialize each sum list with zero.
Expand left: [0] → [0,5] → [0,5,-7,-2].
Expand and sort right: [0] → [0,3] → [0,3,5,8]; initialize best=6.
For x=0, target=6: successor 8 gives distance 2 and predecessor 5 gives 1; best becomes 1.
For x=5, target=1: successor 3 and predecessor 0 give distances 2 and 1. For x=-7, target=13: only predecessor 8 exists, distance 5.
For x=-2, target=8: successor 8 gives distance 0; return 0.

Why It Works

By induction on a half’s processed elements, its sum list covers every subset: old entries exclude the new value, and appended entries include it once. The initial zero covers the empty subset. Every full subset decomposes uniquely into left and right memberships, so all feasible sums are x+y from these lists. For a fixed x, the sorted right list’s nearest value to target=goal-x is either its lower-bound successor or its predecessor; every earlier or later value is at least as far away. Checking both therefore finds the best y for that x, and minimizing over all x finds the global optimum. Repeated sum values represent different memberships but identical objective values, so they need no special removal.

Dry Run

Meet in the Middle: variable states at each step
Left sum x	target=6-x	Lower-bound index	Successor / predecessor	Best
Before search	none	none	right=[0,3,5,8]	6
0	6	3	8 / 5	1
5	1	1	3 / 0	1
-7	13	4 (past end)	none / 8	1
-2	8	3	8 / 5	0

Complexity Analysis

Time Complexity

O(n 2^{n/2})

Space Complexity

O(2^{n/2})

Each half has at most 2^20 sums. Sorting and binary-searching contribute a logarithmic factor proportional to n; generation is linear in list size. Both lists and sorting workspace use exponential half-size storage. Enumeration is iterative, with no recursion depth risk. Full sums have magnitude at most 400,000,000 and distances at most 1,400,000,000; Java uses long intermediates and the int answer is safe. JavaScript Number represents every sum and difference exactly under these bounds.

Code

Solution.java

1import java.util.Arrays;2class Solution {3    private long[] sums(int[] nums, int start, int end) {4        long[] result = new long[1 << (end - start)];5        int size = 1;6        for (int i = start; i < end; i++) {7            for (int j = 0; j < size; j++) result[size + j] = result[j] + nums[i];8            size *= 2;9        }10        return result;11    }12    public int minAbsDifference(int[] nums, int goal) {13        int middle = nums.length / 2;14        long[] left = sums(nums, 0, middle), right = sums(nums, middle, nums.length);15        Arrays.sort(right);16        long best = Math.abs((long) goal);17        for (long x : left) {18            long target = (long) goal - x;19            int lo = 0, hi = right.length;20            while (lo < hi) {21                int mid = lo + (hi - lo) / 2;22                if (right[mid] < target) lo = mid + 1;23                else hi = mid;24            }25            if (lo < right.length) best = Math.min(best, Math.abs(x + right[lo] - goal));26            if (lo > 0) best = Math.min(best, Math.abs(x + right[lo - 1] - goal));27            if (best == 0) return 0;28        }29        return (int) best;30    }31}

Hints

Hint 1

A full 2^40 search is too large, but two 2^20 lists are feasible.

Hint 2

For a left subset sum x, seek the right subset sum nearest goal-x.

Hint 3

Sort one list, use lower bound, check both adjacent candidates and retain zero for the empty subset.

Edge Cases

With one element, one half is empty but still has sum list [0].
The target can lie before the first or after the last right sum; check indices before reading.
Zeros and repeated values create duplicate sums and remain valid.
All positive values with a negative target can make the empty subset optimal.

Common Mistakes and Interview Tips

Appending while looping over the growing list uses the same element repeatedly and can run forever.
JavaScript default sort orders numbers as text; supply a numeric comparator.
Checking only the lower-bound successor misses a closer predecessor.
Pruning sums above goal is invalid when later negative values can reduce them.

Key Takeaway

Meet in the Middle trades two manageable exponential lists for one infeasible full search. Enumeration preserves all possibilities, while sorted nearest-neighbor search avoids testing their Cartesian product.