# 1755 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 = 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`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````class Solution: def minAbsDifference(self, nums: List[int], goal: int) -> int: n = len(nums) # all possible sums of given array def get_all_sums(arr): sums = {0} for a in arr: sums |= {s + a for s in sums} return sums s1 = sorted(get_all_sums(nums[:n//2])) s2 = sorted(get_all_sums(nums[n//2:])) best = math.inf l = 0 r = len(s2) - 1 # find the sum of two sums from s1 and s2 respectively # that gives a value closest to the goal while l < len(s1) and r >= 0: s = s1[l] + s2[r] best = min(best, abs(s - goal)) if s == goal: return 0 elif s < goal: l += 1 else: r -= 1 return best``````