LeetCode 1755 - Closest Subsequence Sum

The problem asks us to find a subsequence of a given integer array nums such that the sum of that subsequence is as close as possible to a given integer goal.

leetcodehardarraytwo-pointersdynamic-programmingbit-manipulationsortingbitmask

LeetCode Problem 1755

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Dynamic Programming, Bit Manipulation, Sorting, Bitmask

Solution

Problem Understanding

The problem asks us to find a subsequence of a given integer array nums such that the sum of that subsequence is as close as possible to a given integer goal. A subsequence can include any subset of elements in their original order, including the possibility of selecting none (which sums to 0) or all elements (which sums to the total of the array). The output is the minimum possible absolute difference between the sum of any subsequence and the target goal.

The constraints tell us that the length of the array nums is small (up to 40), but the values of elements and goal can be large (up to ±10^9). This combination suggests that approaches relying on iterating over all possible sums directly could be feasible with optimization, but naive approaches that generate all 2^40 subsets would be far too slow. Important edge cases include arrays with all positive or all negative numbers, goal being outside the possible sum range, and subsequences that require ignoring all elements (sum = 0).

Approaches

The brute-force approach is straightforward: generate every possible subsequence of nums, compute its sum, and track the absolute difference from goal. This guarantees correctness because it checks all possibilities, but it is too slow. The number of subsequences of an array of length n is 2^n, which grows exponentially. For n = 40, this is roughly 1 trillion, which is infeasible to compute.

The key insight for a more efficient solution is meet-in-the-middle. Because the array length is at most 40, we can split nums into two halves of about 20 elements each. Then we generate all possible sums of subsequences for each half, producing two sets of sums. For each sum in the first half, we can search for the closest complement in the second half to approach the goal. Sorting one half's sums allows us to use binary search to efficiently find the closest sum, reducing the time complexity from O(2^n) to O(2^(n/2) * log(2^(n/2))) = O(2^(n/2) * n).

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(2^n) Generate all subsequences, compute sum, track min difference
Optimal O(2^(n/2) * n) O(2^(n/2)) Meet-in-the-middle: split array, generate sums, binary search for closest complement

Algorithm Walkthrough

  1. Split the array nums into two halves, left and right, of approximately equal length. This reduces the combinatorial explosion, since 2^(n/2) is feasible for n ≤ 40.
  2. Generate all possible subsequence sums for left and right. This can be done using bitmasking or recursive backtracking. For each element, decide whether to include it in the sum.
  3. Sort the list of sums from right. Sorting allows us to perform efficient binary search when looking for the sum that best complements a sum from left to approach the goal.
  4. Initialize a variable min_diff to infinity. This will track the minimum absolute difference found so far.
  5. For each sum s in the left sums, compute the complementary target target = goal - s. Perform binary search in the right sums to find the sum r closest to target. Update min_diff as min(min_diff, abs(s + r - goal)).
  6. After checking all sums from left against the right sums, return min_diff.

Why it works: By generating all sums for each half and combining them, we ensure that every possible subsequence sum of the full array is represented as s_left + s_right. Binary search guarantees that we find the closest match efficiently, and sorting one half preserves correctness.

Python Solution

from typing import List
import bisect

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        def generate_sums(arr: List[int]) -> List[int]:
            sums = [0]
            for num in arr:
                new_sums = [num + s for s in sums]
                sums += new_sums
            return sums
        
        n = len(nums)
        left, right = nums[:n//2], nums[n//2:]
        
        left_sums = generate_sums(left)
        right_sums = generate_sums(right)
        right_sums.sort()
        
        min_diff = float('inf')
        for s in left_sums:
            target = goal - s
            idx = bisect.bisect_left(right_sums, target)
            if idx < len(right_sums):
                min_diff = min(min_diff, abs(s + right_sums[idx] - goal))
            if idx > 0:
                min_diff = min(min_diff, abs(s + right_sums[idx-1] - goal))
        
        return min_diff

The generate_sums function recursively builds all possible sums of subsequences for a given half. Sorting right_sums enables binary search to find the closest complement efficiently. The two binary search checks ensure that we consider both the closest larger and smaller sums to minimize the difference.

Go Solution

import (
    "math"
    "sort"
)

func minAbsDifference(nums []int, goal int) int {
    generateSums := func(arr []int) []int {
        sums := []int{0}
        for _, num := range arr {
            newSums := make([]int, len(sums))
            for i, s := range sums {
                newSums[i] = s + num
            }
            sums = append(sums, newSums...)
        }
        return sums
    }

    n := len(nums)
    leftSums := generateSums(nums[:n/2])
    rightSums := generateSums(nums[n/2:])
    sort.Ints(rightSums)
    
    minDiff := math.MaxInt64
    for _, s := range leftSums {
        target := goal - s
        idx := sort.Search(len(rightSums), func(i int) bool { return rightSums[i] >= target })
        if idx < len(rightSums) {
            diff := abs(s + rightSums[idx] - goal)
            if diff < minDiff {
                minDiff = diff
            }
        }
        if idx > 0 {
            diff := abs(s + rightSums[idx-1] - goal)
            if diff < minDiff {
                minDiff = diff
            }
        }
    }
    return minDiff
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

In Go, slices are dynamically appended, and sorting plus sort.Search provides an efficient way to perform binary search. Care is taken to handle the boundaries of the binary search.

Worked Examples

Example 1: nums = [5, -7, 3, 5], goal = 6

Split: left = [5, -7], right = [3, 5]

Left sums: [0, 5, -7, -2], Right sums: [0, 3, 5, 8]

For each left sum:

  • 0 → target = 6 → closest in right_sums = 5 → abs(0+5-6)=1
  • 5 → target=1 → closest = 0 → abs(5+0-6)=1, 3 → abs(5+3-6)=2 → min=1
  • -7 → target=13 → closest = 8 → abs(-7+8-6)=5
  • -2 → target=8 → closest = 8 → abs(-2+8-6)=0

Result: 0

Complexity Analysis

Measure Complexity Explanation
Time O(2^(n/2) * n) Generate all subsequence sums for each half, sort one half, then binary search for each sum of the other half
Space O(2^(n/2)) Store all sums of one half (or both)

Because n ≤ 40, 2^(n/2) ≈ 2^20 ≈ 1 million, which is computationally feasible.

Test Cases

# Provided examples
assert Solution().minAbsDifference([5,-7,3,5], 6) == 0  # sum matches goal
assert Solution().minAbsDifference([7,-9,15,-2], -5) == 1  # closest sum is -4
assert Solution().minAbsDifference([1,2,3], -7) == 7  # only option is sum=0

# Edge and boundary tests
assert Solution().minAbsDifference([], 0) == 0  # empty array
assert Solution().minAbsDifference([1], 2) == 1  # single element
assert Solution().minAbsDifference([1, -1], 0) == 0  # sum zero possible
assert Solution().minAbsDifference([10**7, -10**7], 5*10**6) == 0  # large numbers
Test Why
[5,-7,3,5],