Closest Subsequence Sum

HARD

Description

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

Checkout 2 different approaches to solve Closest Subsequence Sum. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(n) due to the depth of the recursion stack.

Pros and Cons

Pros:

Simple to conceptualize and implement.

Cons:

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

Code Solutions

Checking out 3 solutions in different languages for Closest Subsequence Sum. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Closest Subsequence Sum

Algorithms:

Sorting

Patterns:

Two PointersDynamic ProgrammingBit ManipulationBitmask

Data Structures:

Array

Companies:

LTI |Sprinklr |