Closest Subsequence Sum solution and explanation
Google
9 more videos on this problem
LeetCode 1755. Closest Subsequence SumHappy Coding · 23:07 · 4K views
花花酱 LeetCode 1755. Closest Subsequence Sum - 刷题找工作 EP382Hua Hua · 15:13 · 1K views
Closest Subsequence Sum | Leetcode 1755 | Meet In The Middle | MITM | Concepts & Questions - 3 | MIKcodestorywithMIK · 26:09 · 1K views
1755. Closest Subsequence Sum (Leetcode Hard)Programming Live with Larry · 40:08 · 1K views
Day 46/75: Problem Name: Closest Subsequence Sum | Leetcode | #75DaysHardLeetcodeCodeInsanity · 5:32 · 766 views
【每日一题】1755. Closest Subsequence Sum, 2/11/2021Huifeng Guan · 33:36 · 724 views
LeetCode 1755. Closest Subsequence Sum宰相小甘罗 · 7:21 · 406 views
Closest Subsequence Sum | Leetcode 1755 | C++Study with Tanuja · 14:17 · 224 views
LeetCode 1755. Closest Subsequence Sum 中文宰相小甘罗 · 5:39 · 167 views
Leetcode 1755. Closest Subsequence SumFearless Learner · 12:21 · 141 views
The problem
You are given an integer array nums and an integer goal.
You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence's elements is sum, then you want to minimize the absolute difference abs(sum - goal).
Return the minimum possible value of abs(sum - goal).
Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.
Example 1:
Input: nums = [5,-7,3,5], goal = 6 Output: 0 Explanation: Choose the whole array as a subsequence, with a sum of 6. This is equal to the goal, so the absolute difference is 0.
Example 2:
Input: nums = [7,-9,15,-2], goal = -5 Output: 1 Explanation: Choose the subsequence [7,-9,-2], with a sum of -4. The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.
Example 3:
Input: nums = [1,2,3], goal = -7 Output: 7
Constraints:
1 <= nums.length <= 40-107 <= nums[i] <= 107-109 <= goal <= 109
Approach overview
Problem Overview: You are given an integer array and a goal value. The task is to choose any subsequence whose sum is as close as possible to the goal and return the absolute difference between that sum and the goal.
Approach 1: Brute Force Subsequence Enumeration (O(2^n) time, O(1) space)
Generate every possible subsequence and compute its sum. For each subset, update the minimum absolute difference between the subset sum and the goal. This approach uses a bitmask to represent which elements are included in the subsequence. While simple, the complexity grows exponentially with 2^n, which becomes infeasible when n approaches 40.
Approach 2: Dynamic Programming Subset Sum Variant (Pseudo-polynomial time, high space)
You can treat the problem like a variation of subset sum using dynamic programming. Maintain reachable sums as you iterate through the array and track the closest value to the goal. Because numbers may be negative and the sum range can be large, the DP state can grow significantly. This makes it impractical for the constraints of this problem, but it helps reason about the search space and pruning strategies.
Approach 3: Meet in the Middle (O(2^(n/2) log 2^(n/2)) time, O(2^(n/2)) space)
The array length can reach 40, which makes 2^40 enumeration impossible. Split the array into two halves of roughly equal size. Generate all subset sums for the left half and all subset sums for the right half using bitmask enumeration. Sort the sums of one half. For each sum in the other half, compute the remaining value needed to reach the goal and use binary search or a two pointers style search to find the closest complement.
This technique reduces the search space dramatically. Instead of exploring 2^n combinations, you process two lists of size about 2^(n/2). After sorting one list, each lookup finds the closest possible combined sum in logarithmic time. Track the minimum absolute difference across all combinations.
Recommended for interviews: Meet in the Middle is the expected solution. Interviewers want to see that you recognize the n ≤ 40 constraint and reduce the exponential search using two halves. Mentioning the brute force approach shows understanding of the problem space, but implementing Meet in the Middle demonstrates strong algorithmic intuition.
Approach 1: Meet in the Middle Approach
The Meet in the Middle approach is effective here due to the constraint of the array's length. By dividing the input array into two halves, you can generate all possible sums for each half and then combine them to find the closest sum to the target.
This method leverages the power of subsets and allows you to efficiently calculate the minimum possible difference by evaluating only a manageable number of subsets compared to calculating every possible subsequence.
from itertools import combinations
def generate_sums(nums):
sum_set = set()
for r in range(len(nums) + 1):
for combo in combinations(nums, r):
sum_set.add(sum(combo))
return list(sum_set)
def min_abs_difference(nums, goal):
n = len(nums)
left, right = nums[:n // 2], nums[n // 2:]
sums_left = generate_sums(left)
sums_right = generate_sums(right)
sums_right.sort()
min_diff = abs(goal)
for s1 in sums_left:
complement = goal - s1
idx = bisect.bisect_left(sums_right, complement)
if idx < len(sums_right):
min_diff = min(min_diff, abs(s1 + sums_right[idx] - goal))
if idx > 0:
min_diff = min(min_diff, abs(s1 + sums_right[idx - 1] - goal))
return min_diff
import bisect
nums = [5, -7, 3, 5]
goal = 6
print(min_abs_difference(nums, goal))import java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = {5, -7, 3, 5};
int goal = 6;
System.out.println(minAbsDifference(nums, goal));
}
public static void generateSums(int[] nums, List<Integer> sums) {
int total = 1 << nums.length;
for (int i = 0; i < total; i++) {
int sum = 0;
for (int j = 0; j < nums.length; j++) {
if ((i & (1 << j)) != 0) {
sum += nums[j];
}
}
sums.add(sum);
}
}
public static int minAbsDifference(int[] nums, int goal) {
int n = nums.length;
List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
generateSums(Arrays.copyOfRange(nums, 0, n / 2), left);
generateSums(Arrays.copyOfRange(nums, n / 2, n), right);
Collections.sort(right);
int minDiff = Math.abs(goal);
for (int s1 : left) {
int complement = goal - s1;
int idx = Collections.binarySearch(right, complement);
if (idx >= 0) {
return 0;
}
idx = -idx - 1;
if (idx < right.size()) {
minDiff = Math.min(minDiff, Math.abs(s1 + right.get(idx) - goal));
}
if (idx > 0) {
minDiff = Math.min(minDiff, Math.abs(s1 + right.get(idx - 1) - goal));
}
}
return minDiff;
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
void generateSums(const vector<int>& nums, vector<int>& sums) {
int total = 1 << nums.size();
for (int i = 0; i < total; ++i) {
int sum = 0;
for (int j = 0; j < nums.size(); ++j) {
if (i & (1 << j)) {
sum += nums[j];
}
}
sums.push_back(sum);
}
}
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size();
vector<int> left(nums.begin(), nums.begin() + n / 2);
vector<int> right(nums.begin() + n / 2, nums.end());
vector<int> sumsLeft, sumsRight;
generateSums(left, sumsLeft);
generateSums(right, sumsRight);
sort(sumsRight.begin(), sumsRight.end());
int minDiff = abs(goal);
for (int s1 : sumsLeft) {
int complement = goal - s1;
auto it = lower_bound(sumsRight.begin(), sumsRight.end(), complement);
if (it != sumsRight.end()) {
minDiff = min(minDiff, abs(s1 + *it - goal));
}
if (it != sumsRight.begin()) {
--it;
minDiff = min(minDiff, abs(s1 + *it - goal));
}
}
return minDiff;
}
int main() {
vector<int> nums = {5, -7, 3, 5};
int goal = 6;
cout << minAbsDifference(nums, goal) << endl;
return 0;
}function generateSums(nums) {
const sumSet = new Set();
const total = 1 << nums.length;
for (let i = 0; i < total; i++) {
let sum = 0;
for (let j = 0; j < nums.length; j++) {
if (i & (1 << j)) {
sum += nums[j];
}
}
sumSet.add(sum);
}
return Array.from(sumSet);
}
function minAbsDifference(nums, goal) {
const n = nums.length;
const left = nums.slice(0, Math.floor(n / 2));
const right = nums.slice(Math.floor(n / 2));
const sumsLeft = generateSums(left);
const sumsRight = generateSums(right);
sumsRight.sort((a, b) => a - b);
let minDiff = Math.abs(goal);
for (const s1 of sumsLeft) {
const complement = goal - s1;
let idx = binarySearch(sumsRight, complement);
if (idx < 0) idx = ~idx;
if (idx < sumsRight.length) minDiff = Math.min(minDiff, Math.abs(s1 + sumsRight[idx] - goal));
if (idx > 0) minDiff = Math.min(minDiff, Math.abs(s1 + sumsRight[idx - 1] - goal));
}
return minDiff;
}
function binarySearch(arr, x) {
let low = 0, high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === x) return mid;
else if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return ~low;
}
console.log(minAbsDifference([5, -7, 3, 5], 6));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void generateSums(int* nums, int numsSize, int* sums, int* size) {
int total = 1 << numsSize;
*size = total;
for (int i = 0; i < total; i++) {
int sum = 0;
for (int j = 0; j < numsSize; j++) {
if (i & (1 << j)) {
sum += nums[j];
}
}
sums[i] = sum;
}
}
int minAbsDifference(int* nums, int numsSize, int goal) {
int n1 = numsSize / 2;
int n2 = numsSize - n1;
int* sums1 = (int*)malloc((1 << n1) * sizeof(int));
int* sums2 = (int*)malloc((1 << n2) * sizeof(int));
int s1Size, s2Size;
generateSums(nums, n1, sums1, &s1Size);
generateSums(nums + n1, n2, sums2, &s2Size);
qsort(sums2, s2Size, sizeof(int), compare);
int minDiff = abs(goal);
for (int i = 0; i < s1Size; i++) {
int complement = goal - sums1[i];
int low = 0, high = s2Size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (sums2[mid] == complement) {
minDiff = 0;
break;
} else if (sums2[mid] < complement) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (minDiff == 0) break;
if (low < s2Size) {
int diff = abs(sums1[i] + sums2[low] - goal);
if (diff < minDiff) minDiff = diff;
}
if (high >= 0) {
int diff = abs(sums1[i] + sums2[high] - goal);
if (diff < minDiff) minDiff = diff;
}
}
free(sums1);
free(sums2);
return minDiff;
}
int main() {
int nums[] = {5, -7, 3, 5};
int goal = 6;
int result = minAbsDifference(nums, 4, goal);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] nums = {5, -7, 3, 5};
int goal = 6;
Console.WriteLine(MinAbsDifference(nums, goal));
}
static void GenerateSums(int[] nums, List<int> sums) {
int total = 1 << nums.Length;
for (int i = 0; i < total; i++) {
int sum = 0;
for (int j = 0; j < nums.Length; j++) {
if ((i & (1 << j)) != 0) {
sum += nums[j];
}
}
sums.Add(sum);
}
}
static int MinAbsDifference(int[] nums, int goal) {
int n = nums.Length;
List<int> left = new List<int>(), right = new List<int>();
GenerateSums(nums[0..(n / 2)], left);
GenerateSums(nums[(n / 2)..n], right);
right.Sort();
int minDiff = Math.Abs(goal);
foreach (int s1 in left) {
int complement = goal - s1;
int idx = right.BinarySearch(complement);
if (idx < 0) idx = ~idx;
if (idx < right.Count) minDiff = Math.Min(minDiff, Math.Abs(s1 + right[idx] - goal));
if (idx > 0) minDiff = Math.Min(minDiff, Math.Abs(s1 + right[idx - 1] - goal));
}
return minDiff;
}
}The Python implementation leverages its built-in libraries to generate subset sums and utilize binary search. Python's itertools and bisect modules are employed for subset generation and search optimization, respectively.
This code splits the list, computes all sums for each subset, and then determines the closest sum to the goal using a sorted list and direct comparisons.
Time Complexity: O(2n/2 log(2n/2))
Space Complexity: O(2n/2)
Approach 2: Default Approach
func minAbsDifference(nums []int, goal int) int {
n := len(nums)
lsum := make([]int, 0)
rsum := make([]int, 0)
dfs(nums[:n/2], &lsum, 0, 0)
dfs(nums[n/2:], &rsum, 0, 0)
sort.Ints(rsum)
res := math.MaxInt32
for _, x := range lsum {
t := goal - x
l, r := 0, len(rsum)
for l < r {
m := int(uint(l+r) >> 1)
if rsum[m] < t {
l = m + 1
} else {
r = m
}
}
if l < len(rsum) {
res = min(res, abs(t-rsum[l]))
}
if l > 0 {
res = min(res, abs(t-rsum[l-1]))
}
}
return res
}
func dfs(nums []int, sum *[]int, i, cur int) {
if i == len(nums) {
*sum = append(*sum, cur)
return
}
dfs(nums, sum, i+1, cur)
dfs(nums, sum, i+1, cur+nums[i])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Meet in the Middle Approach | Time Complexity: O(2n/2 log(2n/2)) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Bitmask Enumeration | O(2^n) | O(1) | Only when n is very small or for conceptual understanding of subsequence generation |
| Dynamic Programming Subset Sum | Pseudo-polynomial | High (depends on sum range) | Useful when numbers are small and sum range is limited |
| Meet in the Middle | O(2^(n/2) log 2^(n/2)) | O(2^(n/2)) | Optimal for n up to 40 by splitting the array and combining subset sums efficiently |
Frequently asked questions
Is Closest Subsequence Sum easy or hard?
Closest Subsequence Sum is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that brute force is too slow and applying the Meet in the Middle technique to reduce the search space.
How to solve Closest Subsequence Sum in O(n)?
An O(n) algorithm is not possible because the problem requires exploring combinations of elements. The best known approach is Meet in the Middle with O(2^(n/2) log n) style complexity, which dramatically reduces the exponential search compared to brute force.
What is the best approach for Closest Subsequence Sum?
The most efficient approach is Meet in the Middle. Split the array into two halves, generate all subset sums for each half, then combine them using sorting and binary search to find the closest sum to the goal. This reduces the complexity from O(2^n) to about O(2^(n/2) log 2^(n/2)).
What data structure is used in Closest Subsequence Sum?
The solution typically uses arrays or lists to store subset sums, along with sorting and binary search. Bitmasking is used to generate subsequences efficiently, and two pointers or binary search help find the closest complement sum.
What is the time complexity of Closest Subsequence Sum?
The optimal Meet in the Middle solution runs in O(2^(n/2) log 2^(n/2)) time and uses O(2^(n/2)) space. Each half of the array generates about 2^(n/2) subset sums, and one list is sorted to allow binary search for the closest complement.
Closest Subsequence Sum Python or Java solution approach?
Python and Java implementations usually generate subset sums for both halves using bitmask loops or recursion. One list is sorted, and for each sum in the other list a binary search finds the value closest to goal minus the current sum.
Is Closest Subsequence Sum asked at Google or Amazon interviews?
Variants of subset sum and Meet in the Middle problems have appeared in interviews at companies like Google, Amazon, and Meta. Interviewers use them to test understanding of exponential search reduction and advanced enumeration strategies.