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

def generate_sums(nums: list[int]) -> list[int]:
    acc = {1 << i: n for i, n in enumerate(accumulate(nums))}
    acc[0] = 0
    sm = sum(nums)
    li = [sm]
    for ss in range((1 << len(nums)) - 1, 0, -1):
        ls1 = ss & -ss
        sm += 2*acc[ls1 >> 1] - acc[ls1]
        li.append(sm)
    li.sort()
    return li


class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        sm1 = generate_sums(nums[len(nums) >> 1:])
        sm2 = generate_sums(nums[:len(nums) >> 1])

        mn = abs(goal)

        i2 = bisect_left(sm2, goal-sm1[0])
        if i2 < len(sm2):
            mn = min(mn, sm1[0]+sm2[i2] - goal)

        i1 = 1
        i2 -= 1
        while i2 >= 0:
            while i1 < len(sm1) and sm1[i1] + sm2[i2] < goal:
                i1 += 1
            if i1 >= len(sm1):
                mn = min(mn, goal - (sm1[-1]+sm2[i2]))
                break
            mn = min(mn, goal - (sm1[i1-1]+sm2[i2]), sm1[i1]+sm2[i2] - goal)
            i2 -= 1

        return mn

105800