Daily DSA: Closest Subsequence Sum (Hard)
Problem Statement
You are given an integer array nums and an integer target. You want to choose a subsequence of nums such that the sum of its elements is as close to target as possible.
Return the minimum absolute difference between the sum of the subsequence and target.
A subsequence of an array is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. (e.g., [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,2] is not).
Examples
Example 1:
- Input:
nums = [5, -7, 35, 4], target = 6 - Output:
1 - Explanation: The subsequence
[5]has a sum of 5, which is at a distance of 1 from 6. This is the minimum possible difference.
Example 2:
- Input:
nums = [7, -9, 15, -2], target = -5 - Output:
1 - Explanation: The subsequence
[7, -9, -2]has a sum of -4, which is at a distance of 1 from -5.
Example 3:
- Input:
nums = [1, 2, 3], target = -7 - Output:
7 - Explanation: The empty subsequence has a sum of 0, which is the closest to -7 (difference of 7).
Constraints
1 <= nums.length <= 40-10^7 <= nums[i] <= 10^7-10^9 <= target <= 10^9
Approach: Meet-in-the-Middle
With nums.length up to 40, a standard brute-force approach to check all $2^{40}$ subsequences is impossible ($2^{40} \approx 10^{12}$). However, we can use the Meet-in-the-middle technique:
- Split the Array: Divide the array into two halves:
left(size $N/2$) andright(size $N - N/2$). - Generate All Sums: Generate all possible subsequence sums for both halves. For each half of size 20, there are $2^{20} \approx 10^6$ sums, which is manageable.
- Sort the Second Half: Sort the sums of the
righthalf to enable binary search. - Binary Search for the Target: Iterate through every sum $S_L$ in the
leftsums. We want to find a sum $S_R$ from therightsums such that $S_L + S_R$ is as close totargetas possible. This is equivalent to finding $S_R$ closest totarget - S_L. - Optimization: Use
std::lower_boundin C++ to find the closest values in the sortedrightsums for each $S_L$.
Time & Space Complexity
- Time Complexity: $O(N \cdot 2^{N/2})$, where $N$ is the length of the array. Generating sums takes $O(2^{N/2})$, sorting takes $O(2^{N/2} \log 2^{N/2})$, and binary search takes $O(2^{N/2} \log 2^{N/2})$.
- Space Complexity: $O(2^{N/2})$ to store the generated subsequence sums for the two halves.
C++ Solution
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class Solution {
public:
void generateSums(int index, int end, long long currentSum, const vector<int>& nums, vector<long long>& sums) {
if (index == end) {
sums.push_back(currentSum);
return;
}
// Choice 1: Include nums[index]
generateSums(index + 1, end, currentSum + nums[index], nums, sums);
// Choice 2: Exclude nums[index]
generateSums(index + 1, end, currentSum, nums, sums);
}
int minAbsDifference(vector<int>& nums, int target) {
int n = nums.size();
vector<long long> leftSums, rightSums;
// Generate all possible sums for the first half
generateSums(0, n / 2, 0, nums, leftSums);
// Generate all possible sums for the second half
generateSums(n / 2, n, 0, nums, rightSums);
// Sort right half to perform binary search
sort(rightSums.begin(), rightSums.end());
long long minDiff = abs(target);
for (long long sL : leftSums) {
long long remaining = target - sL;
// Find the first element in rightSums >= remaining
auto it = lower_bound(rightSums.begin(), rightSums.end(), remaining);
if (it != rightSums.end()) {
minDiff = min(minDiff, abs(remaining - *it));
}
if (it != rightSums.begin()) {
// Check the element just smaller than remaining
minDiff = min(minDiff, abs(remaining - *prev(it)));
}
if (minDiff == 0) return 0; // Early exit
}
return (int)minDiff;
}
};