Closest Subsequence Sum

Hard

#1607Time: 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.2 companies

Patterns

Two Pointers Dynamic Programming Bit Manipulation Bitmask

Algorithms

Sorting

Data structures

Array

Companies

LTI Sprinklr

Prompt

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
-10⁷ <= nums[i] <= 10⁷
-10⁹ <= goal <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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).

1class Solution {2    int minDiff = Integer.MAX_VALUE;3 4    public int minAbsDifference(int[] nums, int goal) {5        // This approach is too slow and will result in a Time Limit Exceeded error6        // for the given constraints (n <= 40).7        findSubsequenceSums(0, 0L, nums, goal);8        return minDiff;9    }10 11    private void findSubsequenceSums(int index, long currentSum, int[] nums, int goal) {12        if (index == nums.length) {13            minDiff = Math.min(minDiff, (int)Math.abs(currentSum - goal));14            return;15        }16 17        // Choice 1: Exclude nums[index]18        findSubsequenceSums(index + 1, currentSum, nums, goal);19 20        // Choice 2: Include nums[index]21        findSubsequenceSums(index + 1, currentSum + nums[index], nums, goal);22    }23}

Complexity

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.

Trade-offs

Pros

Simple to conceptualize and implement.

Cons

Extremely inefficient. The exponential time complexity makes it infeasible for n > 20.

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.

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.

Walkthrough

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:

Split the nums array into two halves.
Generate all 2^(n/2) subsequence sums for the first half and store them in a set sums1 to get unique sums.
Do the same for the second half and store them in sums2.
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.
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.

1import java.util.*;2 3class Solution {4    public int minAbsDifference(int[] nums, int goal) {5        int n = nums.length;6        7        Set<Integer> sums1 = new HashSet<>();8        generateSums(0, 0, nums, n / 2, sums1);9 10        Set<Integer> sums2 = new HashSet<>();11        generateSums(n / 2, 0, nums, n, sums2);12 13        List<Integer> sortedSums2 = new ArrayList<>(sums2);14        Collections.sort(sortedSums2);15 16        int minDiff = Integer.MAX_VALUE;17 18        for (int s1 : sums1) {19            int target = goal - s1;20            21            int idx = Collections.binarySearch(sortedSums2, target);22 23            if (idx >= 0) {24                return 0; // Found a perfect match25            }26            27            int insertionPoint = -(idx + 1);28 29            // Check the element at the insertion point (smallest element >= target)30            if (insertionPoint < sortedSums2.size()) {31                int s2 = sortedSums2.get(insertionPoint);32                minDiff = Math.min(minDiff, Math.abs(target - s2));33            }34            35            // Check the element before the insertion point (largest element < target)36            if (insertionPoint > 0) {37                int s2 = sortedSums2.get(insertionPoint - 1);38                minDiff = Math.min(minDiff, Math.abs(target - s2));39            }40        }41        42        return minDiff;43    }44 45    private void generateSums(int index, int currentSum, int[] nums, int end, Set<Integer> sums) {46        if (index == end) {47            sums.add(currentSum);48            return;49        }50        // Exclude nums[index]51        generateSums(index + 1, currentSum, nums, end, sums);52        // Include nums[index]53        generateSums(index + 1, currentSum + nums[index], nums, end, sums);54    }55}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minAbsDifference(int[] nums, int goal) {4    int n = nums.length;5    List<Integer> lsum = new ArrayList<>();6    List<Integer> rsum = new ArrayList<>();7    dfs(nums, lsum, 0, n / 2, 0);8    dfs(nums, rsum, n / 2, n, 0);9    rsum.sort(Integer : : compareTo);10    int res = Integer.MAX_VALUE;11    for (Integer x : lsum) {12      int target = goal - x;13      int left = 0, right = rsum.size();14      while (left < right) {15        int mid = (left + right) >> 1;16        if (rsum.get(mid) < target) {17          left = mid + 1;18        } else {19          right = mid;20        }21      }22      if (left < rsum.size()) {23        res = Math.min(res, Math.abs(target - rsum.get(left)));24      }25      if (left > 0) {26        res = Math.min(res, Math.abs(target - rsum.get(left - 1)));27      }28    }29    return res;30  }31private32  void dfs(int[] nums, List<Integer> sum, int i, int n, int cur) {33    if (i == n) {34      sum.add(cur);35      return;36    }37    dfs(nums, sum, i + 1, n, cur);38    dfs(nums, sum, i + 1, n, cur + nums[i]);39  }40}

1class Solution {2public:3  int minAbsDifference(vector<int> &nums, int goal) {4    int n = nums.size();5    vector<int> lsum;6    vector<int> rsum;7    dfs(nums, lsum, 0, n / 2, 0);8    dfs(nums, rsum, n / 2, n, 0);9    sort(rsum.begin(), rsum.end());10    int res = INT_MAX;11    for (int x : lsum) {12      int target = goal - x;13      int left = 0, right = rsum.size();14      while (left < right) {15        int mid = (left + right) >> 1;16        if (rsum[mid] < target) {17          left = mid + 1;18        } else {19          right = mid;20        }21      }22      if (left < rsum.size()) {23        res = min(res, abs(target - rsum[left]));24      }25      if (left > 0) {26        res = min(res, abs(target - rsum[left - 1]));27      }28    }29    return res;30  }31 32private:33  void dfs(vector<int> &nums, vector<int> &sum, int i, int n, int cur) {34    if (i == n) {35      sum.emplace_back(cur);36      return;37    }38    dfs(nums, sum, i + 1, n, cur);39    dfs(nums, sum, i + 1, n, cur + nums[i]);40  }41};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem