The Closest Subsequence Sum problem asks you to find a subsequence of a given integer array nums whose sum is as close as possible to a given goal value. A subsequence is any sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. You must return the absolute difference between the sum of the chosen subsequence and the goal.
abs(subsequence_sum - goal).
At first glance, the problem seems to suggest checking all possible subsequences, calculating their sums, and finding which sum is closest to the goal. However, since the number of subsequences is 2^n for an array of length n, this approach quickly becomes infeasible for larger arrays.
To optimize, we look for ways to reduce the search space. One common trick is to split the array into two halves and work with their subset sums separately, known as the meet-in-the-middle technique. This reduces the complexity from 2^n to 2^{n/2}, which is much more manageable for n up to 40.
The key idea is to precompute all possible subset sums for both halves, then combine them efficiently to find the sum closest to the goal.
nums into two halves: left and right.
k, there are 2^k possible subset sums, including the sum 0 (the empty subset).
right). This enables efficient binary search.
left subset sums, calculate the complement needed to reach the goal. Use binary search on the sorted right subset sums to find the sum that, when added to the current left sum, gets as close as possible to the goal.
This approach leverages efficient subset generation and binary search to drastically reduce the total computation required.
Sample Input:
nums = [5, -7, 3, 5], goal = 6
left = [5, -7], right = [3, 5]
left subset sums: 0 (empty), 5, -7, (5 + -7) = -2 → [0, 5, -7, -2]
right subset sums: 0, 3, 5, (3 + 5) = 8 → [0, 3, 5, 8]
right sums: [0, 3, 5, 8]
left sum, binary search in right for closest to goal - left_sum:
left_sum = 0: want closest to 6. right_sum = 5 or 8. 0 + 5 = 5 (diff 1), 0 + 8 = 8 (diff 2).
left_sum = 5: want closest to 1. right_sum = 0 (5 + 0 = 5, diff 1), right_sum = 3 (5 + 3 = 8, diff 2).
left_sum = -7: want closest to 13. right_sum = 8 (-7 + 8 = 1, diff 5).
left_sum = -2: want closest to 8. right_sum = 8 (-2 + 8 = 6, diff 0) → Exact match
0 (subsequence sum equals goal).
O(2^n) time and space, since every possible subset needs to be checked.
n/2, generating all subset sums takes O(2^{n/2}) time and space.O(2^{n/2} \log 2^{n/2}) = O(n 2^{n/2}).
2^{n/2}), binary search in the other half (\log 2^{n/2} = n/2).
O(2^{n/2} \cdot n) time and O(2^{n/2}) space.
This is feasible for n \leq 40.
The Closest Subsequence Sum problem is a classic example where brute-force is impractical, but the "meet-in-the-middle" technique enables an efficient solution. By splitting the array, precomputing all subset sums for each half, and using binary search to combine them, we can quickly find the closest possible sum to the goal. This approach elegantly balances time and space efficiency, making it suitable for moderately sized arrays.
from bisect import bisect_left
def closestSum(nums, goal):
def get_sums(arr):
n = len(arr)
sums = []
for i in range(1 << n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += arr[j]
sums.append(total)
return sums
n = len(nums)
left = nums[:n//2]
right = nums[n//2:]
left_sums = get_sums(left)
right_sums = get_sums(right)
right_sums.sort()
res = float('inf')
for l in left_sums:
rem = goal - l
idx = bisect_left(right_sums, rem)
# check right_sums[idx]
if idx < len(right_sums):
res = min(res, abs(l + right_sums[idx] - goal))
# check right_sums[idx-1]
if idx > 0:
res = min(res, abs(l + right_sums[idx-1] - goal))
return res
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size();
int n1 = n / 2;
int n2 = n - n1;
vector<int> left(nums.begin(), nums.begin() + n1);
vector<int> right(nums.begin() + n1, nums.end());
vector<int> left_sums, right_sums;
// Generate all subset sums for left
for (int i = 0; i < (1 << n1); ++i) {
int sum = 0;
for (int j = 0; j < n1; ++j) {
if ((i >> j) & 1) sum += left[j];
}
left_sums.push_back(sum);
}
// Generate all subset sums for right
for (int i = 0; i < (1 << n2); ++i) {
int sum = 0;
for (int j = 0; j < n2; ++j) {
if ((i >> j) & 1) sum += right[j];
}
right_sums.push_back(sum);
}
sort(right_sums.begin(), right_sums.end());
int res = abs(goal);
for (int l : left_sums) {
int rem = goal - l;
auto it = lower_bound(right_sums.begin(), right_sums.end(), rem);
if (it != right_sums.end()) {
res = min(res, abs(l + *it - goal));
}
if (it != right_sums.begin()) {
--it;
res = min(res, abs(l + *it - goal));
}
}
return res;
}
};
import java.util.*;
class Solution {
public int minAbsDifference(int[] nums, int goal) {
int n = nums.length;
int n1 = n / 2, n2 = n - n1;
int[] left = Arrays.copyOfRange(nums, 0, n1);
int[] right = Arrays.copyOfRange(nums, n1, n);
ArrayList<Integer> leftSums = new ArrayList<>();
ArrayList<Integer> rightSums = new ArrayList<>();
for (int i = 0; i < (1 << n1); i++) {
int sum = 0;
for (int j = 0; j < n1; j++) {
if (((i >> j) & 1) == 1) sum += left[j];
}
leftSums.add(sum);
}
for (int i = 0; i < (1 << n2); i++) {
int sum = 0;
for (int j = 0; j < n2; j++) {
if (((i >> j) & 1) == 1) sum += right[j];
}
rightSums.add(sum);
}
Collections.sort(rightSums);
int res = Math.abs(goal);
for (int l : leftSums) {
int rem = goal - l;
int idx = Collections.binarySearch(rightSums, rem);
if (idx < 0) idx = -idx - 1;
if (idx < rightSums.size())
res = Math.min(res, Math.abs(l + rightSums.get(idx) - goal));
if (idx > 0)
res = Math.min(res, Math.abs(l + rightSums.get(idx - 1) - goal));
}
return res;
}
}
function minAbsDifference(nums, goal) {
function getSums(arr) {
const n = arr.length;
const sums = [];
for (let i = 0; i < (1 << n); ++i) {
let sum = 0;
for (let j = 0; j < n; ++j) {
if ((i >> j) & 1) sum += arr[j];
}
sums.push(sum);
}
return sums;
}
const n = nums.length;
const left = nums.slice(0, Math.floor(n / 2));
const right = nums.slice(Math.floor(n / 2));
const leftSums = getSums(left);
const rightSums = getSums(right);
rightSums.sort((a, b) => a - b);
let res = Math.abs(goal);
for (const l of leftSums) {
const rem = goal - l;
let lo = 0, hi = rightSums.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (rightSums[mid] < rem) lo = mid + 1;
else hi = mid;
}
if (lo < rightSums.length)
res = Math.min(res, Math.abs(l + rightSums[lo] - goal));
if (lo > 0)
res = Math.min(res, Math.abs(l + rightSums[lo - 1] - goal));
}
return res;
}