<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 typing import  List


class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        #import time
        #now = time.time()
        a = nums

        leftsize = len(a)//2
        # if len(a)>10:
        #     leftsize-=1

        rightsize = len(a)-leftsize

        left = []
        right = []
        left.append(0)
        for i in range(leftsize):
            until = len(left)
            for j in range(until):
                left.append(a[i]+left[j])

        right.append(0)
        for i in range(leftsize,len(a)):
            until = len(right)
            for j in range(until):
                right.append(a[i]+right[j])
        # for i in range(1<<leftsize):
        #     thissum = 0
        #     for j in range(leftsize):
        #         if ( i& (1<<j))>0:
        #             thissum+=a[j]
        #     left.append(thissum)

        #
        # for i in range(1<<rightsize):
        #     thissum = 0
        #     for j in range(rightsize):
        #         if ( i& (1<<j))>0:
        #             thissum+=a[j+leftsize]
        #     right.append(thissum)
        #print(time.time()-now)
        left = sorted(left)
        right = sorted(right)
        ans = abs(goal-a[0])

        for thissum in left:
            if thissum+right[-1]<goal:
                ans = min(ans, goal-thissum-right[-1])
                continue
            if thissum+right[0]>goal:
                ans = min(ans,abs(goal-thissum-right[0]))
                continue
            target = goal-thissum

            start = 0
            end = len(right)-1
            while start<=end:
                mid = (start+end)//2
                if right[mid]>target:
                    end = mid-1
                elif right[mid]<target:
                    start = mid+1
                else:
                    break

            for i in range(mid-1,mid+2):
                if i>=0 and i<len(right):
                    ans = min(ans, abs(goal-thissum-right[i]))

        return ans
114800