1755. Closest Subsequence Sum

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

 

Solutions

Solution: Depth-First Search + Binary Search

• Time complexity: O(n*2^n/2)
• Space complexity: O(2^n/2)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
const minAbsDifference = function (nums, goal) {
  const n = nums.length;
  const half = Math.floor(n / 2);
  const lNums = nums.slice(0, half);
  const rNums = nums.slice(half, n);
  let lSums = new Set();
  let rSums = new Set();
  let result = Number.MAX_SAFE_INTEGER;

  const getSums = (values, index, sum, sums) => {
    if (index >= values.length) {
      sums.add(sum);
      return;
    }
    const value = values[index];

    getSums(values, index + 1, sum, sums);
    getSums(values, index + 1, sum + value, sums);
  };

  getSums(lNums, 0, 0, lSums);
  getSums(rNums, 0, 0, rSums);
  lSums = [...lSums];
  rSums = [...rSums].sort((a, b) => a - b);

  const findFirstGreaterEqual = (sums, target) => {
    let left = 0;
    let right = sums.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      sums[mid] >= target ? (right = mid - 1) : (left = mid + 1);
    }

    return left;
  };

  for (const sum of lSums) {
    const index = findFirstGreaterEqual(rSums, goal - sum);

    if (index < rSums.length) {
      result = Math.min(Math.abs(goal - sum - rSums[index]), result);
    }

    if (index > 0) {
      result = Math.min(Math.abs(goal - sum - rSums[index - 1]), result);
    }
  }

  return result;
};