Get started

Closest Subsequence Sum — Hard Problem & Solution

Choose a subsequence of nums (any subset of its elements — possibly none, possibly all) so that its sum is as close as possible to goal.

Problem statement

Choose a subsequence of nums (any subset of its elements — possibly none, possibly all) so that its sum is as close as possible to goal. The empty subsequence has sum 0.

Return the minimum possible value of abs(sum - goal).

Example 1

Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: The whole array sums to 6.

Example 2

Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: `[7,-9,-2]` sums to -4.

Example 3

Input: nums = [1,2,3], goal = -7
Output: 7
Explanation: Every element is positive, so the empty subsequence (sum 0) is closest.

Constraints

  • 1 <= nums.length <= 40
  • -10^7 <= nums[i] <= 10^7
  • -10^9 <= goal <= 10^9

How to solve Closest Subsequence Sum

Meet in the middle: enumerate the subset sums of each half separately, then pair them up with a sorted search instead of trying all 2^n combinations.

Approach

  1. Split nums into halves A and B.
  2. Generate all subset sums of A (L) and of B (R) by doubling a list: start with [0], and for each element append every existing sum plus that element.
  3. Sort R. For each s in L, find the first r in R with r >= goal - s; check both it and its predecessor, updating best = min(best, |s + r - goal|).
  4. Return best (stop early if it reaches 0).

Why it works

Every subsequence splits uniquely into its part in A and its part in B, so the candidate sums are exactly s + r with s ∈ L, r ∈ R. For a fixed s, the best r is the one closest to goal - s, which in sorted order is one of the two neighbours of the insertion point.

Complexity

  • Time — O(2^(n/2) · n)
  • Space — O(2^(n/2))

Pitfalls

  • Do not forget the empty subsequence: both half-lists must contain 0.
  • Sums reach ±4 · 10^8 and the difference to goal up to 1.4 · 10^9 — it still fits in 32 bits, but use 64-bit to be safe.
  • A DP over sums is hopeless here: the values span ±4 · 10^8.

Reference solution

Python

from typing import List
from bisect import bisect_left

def minAbsDifference(nums: List[int], goal: int) -> int:
    half = len(nums) // 2

    def sums(arr):
        res = [0]
        for v in arr:
            res += [s + v for s in res]
        return res

    left = sums(nums[:half])
    right = sorted(sums(nums[half:]))
    best = abs(goal)
    for s in left:
        i = bisect_left(right, goal - s)
        if i < len(right):
            best = min(best, abs(s + right[i] - goal))
        if i > 0:
            best = min(best, abs(s + right[i - 1] - goal))
        if best == 0:
            return 0
    return best

JavaScript

var minAbsDifference = function(nums, goal) {
    var half = nums.length >> 1;
    var sums = function(lo, hi) {
        var res = [0];
        for (var i = lo; i < hi; i++) {
            var len = res.length;
            for (var j = 0; j < len; j++) res.push(res[j] + nums[i]);
        }
        return res;
    };
    var left = sums(0, half);
    var right = sums(half, nums.length).sort(function(a, b) { return a - b; });
    var best = Math.abs(goal);
    for (var t = 0; t < left.length && best > 0; t++) {
        var need = goal - left[t];
        var lo = 0, hi = right.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (right[mid] < need) lo = mid + 1; else hi = mid;
        }
        if (lo < right.length) best = Math.min(best, Math.abs(left[t] + right[lo] - goal));
        if (lo > 0) best = Math.min(best, Math.abs(left[t] + right[lo - 1] - goal));
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms