Scale Engineer

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 PointersDynamic ProgrammingBit ManipulationBitmask
Algorithms
Sorting
Data structures
Array
Companies
LTISprinklr

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
  • -107 <= nums[i] <= 107
  • -109 <= goal <= 109

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

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.

Solutions

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]);  }}

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 →

Next problem