In this guide, you will get 1755. Closest Subsequence Sum LeetCode Solution with the best time and space complexity. The solution to Closest Subsequence Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
1755. Closest Subsequence Sum LeetCode Solution in C++
class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
const int n = nums.size() / 2;
const vector<int> lNums(nums.begin(), nums.begin() + n);
const vector<int> rNums(nums.begin() + n, nums.end());
int ans = INT_MAX;
vector<int> lSums;
vector<int> rSums;
dfs(lNums, 0, 0, lSums);
dfs(rNums, 0, 0, rSums);
ranges::sort(rSums);
for (const int lSum : lSums) {
const int i = firstGreaterEqual(rSums, goal - lSum);
if (i < rSums.size()) // 2^n
ans = min(ans, abs(goal - lSum - rSums[i]));
if (i > 0)
ans = min(ans, abs(goal - lSum - rSums[i - 1]));
}
return ans;
}
private:
void dfs(const vector<int>& arr, int i, int path, vector<int>& sums) {
if (i == arr.size()) {
sums.push_back(path);
return;
}
dfs(arr, i + 1, path + arr[i], sums);
dfs(arr, i + 1, path, sums);
}
int firstGreaterEqual(const vector<int>& arr, int target) {
return ranges::lower_bound(arr, target) - arr.begin();
}
}; /* code provided by PROGIEZ */
1755. Closest Subsequence Sum LeetCode Solution in Java
class Solution {
public int minAbsDifference(int[] nums, int goal) {
final int n = nums.length / 2;
final int[] lNums = Arrays.copyOfRange(nums, 0, n);
final int[] rNums = Arrays.copyOfRange(nums, n, nums.length);
int ans = Integer.MAX_VALUE;
List<Integer> lSums = new ArrayList<>();
List<Integer> rSums = new ArrayList<>();
dfs(lNums, 0, 0, lSums);
dfs(rNums, 0, 0, rSums);
Collections.sort(rSums);
for (final int lSum : lSums) {
final int i = firstGreaterEqual(rSums, goal - lSum);
if (i < rSums.size()) // 2^n
ans = Math.min(ans, Math.abs(goal - lSum - rSums.get(i)));
if (i > 0)
ans = Math.min(ans, Math.abs(goal - lSum - rSums.get(i - 1)));
}
return ans;
}
private void dfs(int[] arr, int i, int path, List<Integer> sums) {
if (i == arr.length) {
sums.add(path);
return;
}
dfs(arr, i + 1, path + arr[i], sums);
dfs(arr, i + 1, path, sums);
}
private int firstGreaterEqual(List<Integer> arr, int target) {
final int i = Collections.binarySearch(arr, target);
return i < 0 ? -i - 1 : i;
}
} // code provided by PROGIEZ
1755. Closest Subsequence Sum LeetCode Solution in Python
class Solution:
def minAbsDifference(self, nums: list[int], goal: int) -> int:
n = len(nums) // 2
ans = math.inf
lSums = []
rSums = []
def dfs(arr: list[int], i: int, path: int, sums: list[int]) -> None:
if i == len(arr):
sums.append(path)
return
dfs(arr, i + 1, path + arr[i], sums)
dfs(arr, i + 1, path, sums)
dfs(nums[:n], 0, 0, lSums)
dfs(nums[n:], 0, 0, rSums)
rSums.sort()
for lSum in lSums:
i = bisect_left(rSums, goal - lSum)
if i < len(rSums): # 2^n
ans = min(ans, abs(goal - lSum - rSums[i]))
if i > 0:
ans = min(ans, abs(goal - lSum - rSums[i - 1]))
return ans # code by PROGIEZ
