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.
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.
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.
| Approach | Complexity |
|---|---|
| Meet in the Middle Approach | Time Complexity: O(2n/2 log(2n/2)) due to generation and sorting of all subset sums. |
| Default Approach | — |
| 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 |
LeetCode 1755. Closest Subsequence Sum • Happy Coding • 4,380 views views
Watch 9 more video solutions →Practice Closest Subsequence Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor