<p>You are given an integer array <code>nums</code> and an integer <code>goal</code>.</p>

<p>You want to choose a subsequence of <code>nums</code> such that the sum of its elements is the closest possible to <code>goal</code>. That is, if the sum of the subsequence&#39;s elements is <code>sum</code>, then you want to <strong>minimize the absolute difference</strong> <code>abs(sum - goal)</code>.</p>

<p>Return <em>the <strong>minimum</strong> possible value of</em> <code>abs(sum - goal)</code>.</p>

<p>Note that a subsequence of an array is an array formed by removing some elements <strong>(possibly all or none)</strong> of the original array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,-7,3,5], goal = 6
<strong>Output:</strong> 0
<strong>Explanation:</strong> Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,-9,15,-2], goal = -5
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3], goal = -7
<strong>Output:</strong> 7
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 40</code></li>
	<li><code>-10<sup>7</sup> &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= goal &lt;= 10<sup>9</sup></code></li>
</ul>

from itertools import combinations

class Solution:
    def minAbsDifference(self, nums, goal):
        n = len(nums)
        
        # Generate all possible sums for the first half and the second half
        first_half_sums = self.generate_sums(nums[:n//2])
        second_half_sums = self.generate_sums(nums[n//2:])
        
        # Sort the second half sums to enable binary search
        second_half_sums.sort()
        
        # Find the closest sum to the goal using binary search
        closest_sum = float('inf')
        for sum_first_half in first_half_sums:
            target = goal - sum_first_half
            # Find the closest sum in second_half_sums to the target
            idx = self.binary_search(second_half_sums, target)
            closest_sum = min(closest_sum, abs(sum_first_half + second_half_sums[idx] - goal))
            # If the next index is within bounds, check that too
            if idx + 1 < len(second_half_sums):
                closest_sum = min(closest_sum, abs(sum_first_half + second_half_sums[idx + 1] - goal))
            # If the previous index is within bounds, check that too
            if idx - 1 >= 0:
                closest_sum = min(closest_sum, abs(sum_first_half + second_half_sums[idx - 1] - goal))
        
        return closest_sum
    
    def generate_sums(self, arr):
        sums = [0]
        for num in arr:
            sums += [s + num for s in sums]
        return sums
    
    def binary_search(self, arr, target):
        left, right = 0, len(arr) - 1
        while left < right:
            mid = (left + right) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

# Example usage:
solution = Solution()
nums = [5, -7, 3, 5]
goal = 6
print(solution.minAbsDifference(nums, goal))  # Output: 0
109500