Watch 10 video solutions for Closest Subsequence Sum, a hard level problem involving Array, Two Pointers, Dynamic Programming. This walkthrough by Happy Coding has 4,380 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem 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 | 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 |