Find the Closest Subsequence Sum to Target
Given an integer array arr[] and an integer target. The task is to find a subsequence of arr such that the absolute difference between the sum of its elements and target is minimized. Return the minimum possible value of abs(sum – target).
Note: Subsequence of an array is an array formed by removing some (possibly all or none) of the original elements.
Examples:
Input: arr = [5, -7, 3, 5], target = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6. This is equal to the target, so the absolute difference is 0.Input: arr = [1, 2, 3], target = -7
Output: 7
Explanation: Choosing no elements results in a sum of 0, which is the closest to -7.
Approach:
To solve this problem, we need to find a way to explore all possible subsequences efficiently. One effective approach is to use the “meet in the middle” technique. We split the array into two halves and consider all possible sums for each half. By doing so, we reduce the problem size and can find the closest sum to the target efficiently using binary search.
Steps-by-step approach:
- Split the array arr into two halves.
- Calculate all possible sums of subsequences for each half.
- Sort the list of sums from the second half.
- For each sum in the first half, use binary search on the sorted sums of the second half to find the closest possible sum to the target.
- Keep track of the minimum absolute difference between the total sum and the target.
- Return the minimum absolute difference found.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Helper function to generate all possible sums of
// subsequences of a given vector
void generateSums(const vector<int>& nums, int start,
int end, vector<int>& sums)
{
int n = end - start;
for (int i = 0; i < (1 << n); ++i) {
int sum = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
sum += nums[start + j];
}
}
sums.push_back(sum);
}
}
int minAbsDifference(vector<int>& nums, int goal)
{
int n = nums.size();
vector<int> leftSums, rightSums;
// Step 1: Split the array and generate all possible
// sums for each half
generateSums(nums, 0, n / 2, leftSums);
generateSums(nums, n / 2, n, rightSums);
// Step 2: Sort the sums of the second half
sort(rightSums.begin(), rightSums.end());
int minDiff = abs(goal); // Initial difference assuming
// no elements are chosen
// Step 3: For each sum in the first half, find the
// closest sum in the second half using binary search
for (int leftSum : leftSums) {
int remaining = goal - leftSum;
auto it = lower_bound(rightSums.begin(),
rightSums.end(), remaining);
// Check the closest values found by binary search
if (it != rightSums.end()) {
minDiff = min(minDiff, abs(remaining - *it));
}
if (it != rightSums.begin()) {
minDiff
= min(minDiff, abs(remaining - *(it - 1)));
}
}
return minDiff;
}
// Driver code
int main()
{
vector<int> arr = { 5, -7, 3, 5 };
int target = 6;
cout << minAbsDifference(arr, target) << endl;
return 0;
}
import java.util.*;
public class MinAbsDifference {
// Helper function to generate all possible sums of
// subsequences of a given array
public static void generateSums(List<Integer> nums,
int start, int end,
List<Integer> sums)
{
int n = end - start;
for (int i = 0; i < (1 << n); ++i) {
int sum = 0;
for (int j = 0; j < n; ++j) {
if ((i & (1 << j)) != 0) {
sum += nums.get(start + j);
}
}
sums.add(sum);
}
}
public static int minAbsDifference(List<Integer> nums,
int goal)
{
int n = nums.size();
List<Integer> leftSums = new ArrayList<>();
List<Integer> rightSums = new ArrayList<>();
// Step 1: Split the array and generate all possible
// sums for each half
generateSums(nums, 0, n / 2, leftSums);
generateSums(nums, n / 2, n, rightSums);
// Step 2: Sort the sums of the second half
Collections.sort(rightSums);
int minDiff
= Math.abs(goal); // Initial difference assuming
// no elements are chosen
// Step 3: For each sum in the first half, find the
// closest sum in the second half using binary
// search
for (int leftSum : leftSums) {
int remaining = goal - leftSum;
int pos = Collections.binarySearch(rightSums,
remaining);
if (pos >= 0) {
// Exact match found
return 0;
}
else {
pos = -pos - 1; // Binary search returned
// insertion point
}
// Check the closest values found by binary
// search
if (pos < rightSums.size()) {
minDiff = Math.min(
minDiff,
Math.abs(remaining
- rightSums.get(pos)));
}
if (pos > 0) {
minDiff = Math.min(
minDiff,
Math.abs(remaining
- rightSums.get(pos - 1)));
}
}
return minDiff;
}
public static void main(String[] args)
{
List<Integer> arr = Arrays.asList(5, -7, 3, 5);
int target = 6;
System.out.println(minAbsDifference(arr, target));
}
}
// This code is contributed by Shivam Gupta
Output
0
Time Complexity: O(2^n/2)
Auxiliary Space: O(2^n/2)