Skip to main content
Talentd

Closest Subsequence Sum - Solution & Explanation

HardArrayTwo PointersDynamic ProgrammingBit Manipulation13 min readAsked at: Google, Sprinklr, Lti
Practice this problem

Problem Statement

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.

The solution involves dividing the input array into two halves and calculating all possible sums using subsets of these halves. The sums are then sorted and a binary search is used to find the closest possible sum to the goal.

Firstly, it generates all subset sums of both halves. Then, for each sum of the first half, it tries to find the best complementary sum from the second half. By sorting one of the lists of sums, we can use binary search to efficiently find the minimum possible difference from the target goal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2n/2 log(2n/2)) due to generation and sorting of all subset sums.
Space Complexity: O(2n/2) for storing the subset sums.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Meet in the Middle Approach

Time Complexity: O(2n/2 log(2n/2)) due to generation and sorting of all subset sums.
Space Complexity: O(2n/2) for storing the subset sums.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Bitmask EnumerationO(2^n)O(1)Only when n is very small or for conceptual understanding of subsequence generation
Dynamic Programming Subset SumPseudo-polynomialHigh (depends on sum range)Useful when numbers are small and sum range is limited
Meet in the MiddleO(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

Video Solution

LeetCode 1755. Closest Subsequence Sum • Happy Coding • 4,429 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Closest Subsequence Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Sum of Subsequence Powers

Next

Minimize the Difference Between Target and Chosen Elements