Closest Subsequence Sum
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 = 6Output
0Choose the whole array as a subsequence, with a sum of 6, which equals the goal so the absolute difference is 0.
Example 2
Input
nums = [7,-9,15,-2], goal = -5Output
1Choose the subsequence [7, -9, -2], with a sum of -4, giving abs(-4 - (-5)) = 1, which is the minimum.
Constraints
- 1 <= nums.length <= 40
- -10^7 <= nums[i] <= 10^7
- -10^9 <= goal <= 10^9
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.