# Closest Subsequence Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/closest-subsequence-sum)
Canonical: https://scaleengineer.com/dsa/problems/closest-subsequence-sum
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [LTI](https://scaleengineer.com/companies/lti), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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`

# Approaches
## Brute Force via Recursion
The most intuitive approach is to generate every possible subsequence, calculate its sum, and find the one that results in the minimum absolute difference from the `goal`. Since for each element we can either include it or not, there are `2^n` possible subsequences.
**Time:** O(2^n), where `n` is the number of elements in `nums`. The recursion tree has `2^n` leaves, each corresponding to a unique subsequence. · **Space:** O(n) due to the depth of the recursion stack.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient. The exponential time complexity makes it infeasible for `n > 20`.
### Explanation
We can implement this using a recursive backtracking function. The function, say `findSums(index, currentSum)`, explores both possibilities for each element `nums[index]`: including it in the subsequence or excluding it.
The recursion proceeds as follows:
- The state is defined by the current `index` in the `nums` array and the `currentSum` of the subsequence built so far.
- The base case for the recursion is when `index` reaches the end of the array. At this point, we have a complete subsequence sum. We calculate `abs(currentSum - goal)` and update a global minimum difference if the new difference is smaller.
- In the recursive step, we make two calls:
  1. `findSums(index + 1, currentSum)`: This corresponds to not including `nums[index]` in the subsequence.
  2. `findSums(index + 1, currentSum + nums[index])`: This corresponds to including `nums[index]`.
The initial call would be `findSums(0, 0)`.
```java
class Solution {
    int minDiff = Integer.MAX_VALUE;

    public int minAbsDifference(int[] nums, int goal) {
        // This approach is too slow and will result in a Time Limit Exceeded error
        // for the given constraints (n <= 40).
        findSubsequenceSums(0, 0L, nums, goal);
        return minDiff;
    }

    private void findSubsequenceSums(int index, long currentSum, int[] nums, int goal) {
        if (index == nums.length) {
            minDiff = Math.min(minDiff, (int)Math.abs(currentSum - goal));
            return;
        }

        // Choice 1: Exclude nums[index]
        findSubsequenceSums(index + 1, currentSum, nums, goal);

        // Choice 2: Include nums[index]
        findSubsequenceSums(index + 1, currentSum + nums[index], nums, goal);
    }
}
```
### Algorithm
- Initialize a global variable `minDiff` to `Integer.MAX_VALUE`.
- Define a recursive function `findSubsequenceSums(index, currentSum)`.
- Base Case: If `index` equals the length of `nums`, calculate `abs(currentSum - goal)` and update `minDiff = min(minDiff, abs(currentSum - goal))`. Then return.
- Recursive Step: Make two recursive calls:
  1. `findSubsequenceSums(index + 1, currentSum)` (element `nums[index]` is not included).
  2. `findSubsequenceSums(index + 1, currentSum + nums[index])` (element `nums[index]` is included).
- Start the process by calling `findSubsequenceSums(0, 0)`.
- Return `minDiff`.

## Meet-in-the-Middle (Split and Merge)
Given the constraint `n <= 40`, a brute-force O(2^n) solution is too slow. However, `2^(n/2)` (i.e., `2^20`) is manageable. This suggests a 'meet-in-the-middle' strategy. We split the array into two halves, generate all possible subsequence sums for each half independently, and then combine the sums from the two halves to find the overall best solution.
**Time:** O(n * 2^(n/2)). Let `k = n/2`. Generating sums for each half takes O(2^k). Sorting one list of sums takes O(2^k * log(2^k)) = O(k * 2^k). The final loop involves iterating through `2^k` sums and performing a binary search (O(k)) for each, resulting in O(k * 2^k). The dominant term is O(k * 2^k) which is O(n * 2^(n/2)). · **Space:** O(2^(n/2)) to store the subsequence sums for both halves.
**Pros:** Significantly more efficient than brute force.; Passes the given constraints for `n <= 40`.
**Cons:** More complex to implement than the brute-force approach.; Requires significant memory to store the `2^(n/2)` sums.
### Explanation
The core idea is that any subsequence sum of the original array is a sum of a subsequence from the first half and a subsequence from the second half.
The steps are as follows:
1.  Split the `nums` array into two halves.
2.  Generate all `2^(n/2)` subsequence sums for the first half and store them in a set `sums1` to get unique sums.
3.  Do the same for the second half and store them in `sums2`.
4.  Now, for each sum `s1` from `sums1`, we need to find a sum `s2` from `sums2` that makes `s1 + s2` as close to `goal` as possible. This is equivalent to finding an `s2` that is closest to `target = goal - s1`.
5.  To do this efficiently, we can convert `sums2` to a sorted list and use binary search for each `s1`. For a given `target`, binary search helps us find the two elements in `sums2` that are closest to the `target` (one just smaller, one just larger). We check both and update our minimum difference.
The overall minimum difference is the minimum found across all `s1` values.
```java
import java.util.*;

class Solution {
    public int minAbsDifference(int[] nums, int goal) {
        int n = nums.length;
        
        Set<Integer> sums1 = new HashSet<>();
        generateSums(0, 0, nums, n / 2, sums1);

        Set<Integer> sums2 = new HashSet<>();
        generateSums(n / 2, 0, nums, n, sums2);

        List<Integer> sortedSums2 = new ArrayList<>(sums2);
        Collections.sort(sortedSums2);

        int minDiff = Integer.MAX_VALUE;

        for (int s1 : sums1) {
            int target = goal - s1;
            
            int idx = Collections.binarySearch(sortedSums2, target);

            if (idx >= 0) {
                return 0; // Found a perfect match
            }
            
            int insertionPoint = -(idx + 1);

            // Check the element at the insertion point (smallest element >= target)
            if (insertionPoint < sortedSums2.size()) {
                int s2 = sortedSums2.get(insertionPoint);
                minDiff = Math.min(minDiff, Math.abs(target - s2));
            }
            
            // Check the element before the insertion point (largest element < target)
            if (insertionPoint > 0) {
                int s2 = sortedSums2.get(insertionPoint - 1);
                minDiff = Math.min(minDiff, Math.abs(target - s2));
            }
        }
        
        return minDiff;
    }

    private void generateSums(int index, int currentSum, int[] nums, int end, Set<Integer> sums) {
        if (index == end) {
            sums.add(currentSum);
            return;
        }
        // Exclude nums[index]
        generateSums(index + 1, currentSum, nums, end, sums);
        // Include nums[index]
        generateSums(index + 1, currentSum + nums[index], nums, end, sums);
    }
}
```
### Algorithm
- Split the input array `nums` into two halves, `left` and `right`.
- Generate all possible subsequence sums for the `left` half. Store the unique sums in a set `sums1`.
- Generate all possible subsequence sums for the `right` half. Store the unique sums in a set `sums2`.
- Convert `sums2` into a sorted list, `sortedSums2`, for efficient searching.
- Initialize `minDiff` to `Integer.MAX_VALUE`.
- Iterate through each sum `s1` in `sums1`:
  - Calculate the `target` value we need from the second half: `target = goal - s1`.
  - Perform a binary search for `target` in `sortedSums2`.
  - If `target` is found, the difference is 0. Return 0 immediately.
  - If `target` is not found, the binary search returns an `insertionPoint`. The two candidates in `sortedSums2` closest to `target` are at `insertionPoint` and `insertionPoint - 1` (if they exist).
  - Calculate the difference for these candidates: `abs(target - candidate)` and update `minDiff`.
- After iterating through all `s1`, return `minDiff`.

# Solutions
### Java

```java
class Solution {
public
  int minAbsDifference(int[] nums, int goal) {
    int n = nums.length;
    List<Integer> lsum = new ArrayList<>();
    List<Integer> rsum = new ArrayList<>();
    dfs(nums, lsum, 0, n / 2, 0);
    dfs(nums, rsum, n / 2, n, 0);
    rsum.sort(Integer : : compareTo);
    int res = Integer.MAX_VALUE;
    for (Integer x : lsum) {
      int target = goal - x;
      int left = 0, right = rsum.size();
      while (left < right) {
        int mid = (left + right) >> 1;
        if (rsum.get(mid) < target) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      if (left < rsum.size()) {
        res = Math.min(res, Math.abs(target - rsum.get(left)));
      }
      if (left > 0) {
        res = Math.min(res, Math.abs(target - rsum.get(left - 1)));
      }
    }
    return res;
  }
private
  void dfs(int[] nums, List<Integer> sum, int i, int n, int cur) {
    if (i == n) {
      sum.add(cur);
      return;
    }
    dfs(nums, sum, i + 1, n, cur);
    dfs(nums, sum, i + 1, n, cur + nums[i]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minAbsDifference(vector<int> &nums, int goal) {
    int n = nums.size();
    vector<int> lsum;
    vector<int> rsum;
    dfs(nums, lsum, 0, n / 2, 0);
    dfs(nums, rsum, n / 2, n, 0);
    sort(rsum.begin(), rsum.end());
    int res = INT_MAX;
    for (int x : lsum) {
      int target = goal - x;
      int left = 0, right = rsum.size();
      while (left < right) {
        int mid = (left + right) >> 1;
        if (rsum[mid] < target) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      if (left < rsum.size()) {
        res = min(res, abs(target - rsum[left]));
      }
      if (left > 0) {
        res = min(res, abs(target - rsum[left - 1]));
      }
    }
    return res;
  }

private:
  void dfs(vector<int> &nums, vector<int> &sum, int i, int n, int cur) {
    if (i == n) {
      sum.emplace_back(cur);
      return;
    }
    dfs(nums, sum, i + 1, n, cur);
    dfs(nums, sum, i + 1, n, cur + nums[i]);
  }
};

```

### Python

```python
class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int: n = len(nums) left = set() right = set() self . getSubSeqSum(0, 0, nums[: n // 2], left) self . getSubSeqSum(0, 0, nums[n // 2:], right) result = inf right = sorted(right) rl = len(right) for l in left: remaining = goal - l idx = bisect_left(right, remaining) if idx < rl: result = min(result, abs(remaining - right[idx])) if idx > 0: result = min(result, abs(remaining - right[idx - 1])) return result def getSubSeqSum(self, i: int, curr: int, arr: List[int], result: Set[int]): if i == len(arr): result . add(curr) return self . getSubSeqSum(i + 1, curr, arr, result) self . getSubSeqSum(i + 1, curr + arr[i], arr, result)

```