<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>

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        if len(nums) == 1:
            return min(abs(goal), abs(nums[0] - goal))

        mid = len(nums) // 2
        left = nums[:mid]
        right = nums[mid:]

        # get all the subarray sum of an array
        def helper(arr):
            res = set()
            res.add(0)
            res.add(arr[0])
            for i in range(1, len(arr)):
                newRes = res.copy()
                for num in res:
                    newRes.add(num + arr[i])
                newRes.add(num)
                res = newRes
            return res
        leftSet = helper(left)
        rightSet = helper(right)
        rightSet = list(rightSet)
        rightSet.sort()

        # binary search
        def search(arr, target):
            left = 0
            right = len(arr) - 1
            while left <= right:
                mid = left + (right - left)//2
                if arr[mid] == target:
                    return 0
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            candidates = []
            if left < len(arr):
                candidates.append(abs(arr[left] - target))
            if right >= 0:
                candidates.append(abs(arr[right] - target))
            return min(candidates)
             
        minimum = 2 ** 31

        for x in leftSet:
            difference = search(rightSet, goal - x)
            minimum = min(difference, minimum)
        return minimum



        
180500