Problem 38.5 · Advanced Search and Divide & ConquerHard

Closest Subsequence Sum

PatternDivide and Conquer Binary Search on an Index

What it teaches: Meet in the middle: 2²⁰ sums per half, sort one, binary search from the other.

Practise it on judges as “Closest Subsequence Sum”.

In plain words

You may pick any group of the numbers (or none) and add them up; you want the total as close to a goal as possible. Trying every group of 40 numbers is far too many. Split the numbers into two halves, list every total for each half, sort one list, and for each left total binary-search the right list for the partner that lands nearest the goal.

Return the smallest |sum − goal|. Example: nums = [7, -9, 15, -2], goal = -5 → 1.

The problem

Choose any subsequence (possibly empty) of nums. Return the minimum possible |sum − goal|.

Example 1

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

Constraints

1 ≤ n ≤ 40
|nums[i]| ≤ 10⁷
|goal| ≤ 10⁹

Pattern clues in the wording

→ n ≤ 40
→ Subset sum closest to a target
→ Values too large for knapsack DP

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public int minAbsDifference(int[] nums, int goal) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	nums = [5,-7,3,5] goal = 6	0
2	nums = [7,-9,15,-2] goal = -5	1
3	nums = [1,2,3] goal = -7	7

From slow to fast

Approaches

1. Meet in the middle · O(2^(n/2) × n)

Meet in the middle

Time O(2^(n/2) × n) Space O(2^(n/2))

sums(half) builds all subset sums iteratively. Sort right sums; for each left sum find the closest right sum to goal − left with a lower bound and its predecessor.

▶ Dry run: Two halves, sort one, search for the partnernums = [7, -9, 15, -2], goal = -5

left sums of [7, -9](list)

07-9-2

right sums of [15, -2](list)

015-213

Step 1/5Every subset total of each half: 4 totals each instead of 16 for the whole array.

Approach 1

import java.util.Arrays;

class Solution {
    public int minAbsDifference(int[] nums, int goal) {
        int half = nums.length / 2;
        long[] left = sums(nums, 0, half), right = sums(nums, half, nums.length);
        Arrays.sort(right);
        long best = Long.MAX_VALUE;
        for (long a : left) {
            long want = goal - a;
            int lo = 0, hi = right.length;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (right[mid] < want) lo = mid + 1; else hi = mid;
            }
            if (lo < right.length) best = Math.min(best, Math.abs(a + right[lo] - goal));
            if (lo > 0) best = Math.min(best, Math.abs(a + right[lo - 1] - goal));
        }
        return (int) best;
    }

    private long[] sums(int[] nums, int from, int to) {
        long[] s = new long[1 << (to - from)];
        int size = 1;
        for (int i = from; i < to; i++) {
            for (int j = 0; j < size; j++) s[size + j] = s[j] + nums[i];
            size *= 2;
        }
        return s;
    }
}

Verdict: 2⁴⁰ brute force is impossible; this is about 2 million sums.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty subsequence is best (sum 0)
n = 1

Mistakes people make

Knapsack DP over sums (range of ±4 × 10⁸ is too large).

Interview

Follow-up questions

Can the join be done without binary search?

Command Palette

The problem

Approaches

Meet in the middle

Edge cases and common mistakes

Follow-up questions