<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
import sys
import heapq
import bisect

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        mid = len( nums ) // 2
        l_half = nums[:mid]
        r_half = nums[mid:]

        def enum_subseq_sums( value_list, cur_index, cur_sum, result_list ):
            result_list[cur_sum] = 1

            if cur_index >= len(value_list):
                return

            enum_subseq_sums( value_list, cur_index+1, cur_sum + value_list[cur_index], result_list )
            enum_subseq_sums( value_list, cur_index+1, cur_sum, result_list )

        ls_subseq_sums = {}
        rs_subseq_sums = {}

        enum_subseq_sums( l_half, 0, 0, ls_subseq_sums )
        enum_subseq_sums( r_half, 0, 0, rs_subseq_sums )

        result = sys.maxsize

        l_sums = sorted( list( ls_subseq_sums ) )
        r_sums = sorted( list( rs_subseq_sums ) )

        # print( l_sums )
        # print( r_sums )

        for l_sum in l_sums:
            index = bisect.bisect_left( r_sums, goal - l_sum )

            # not too far right
            if index < len(r_sums):
                result = min( result, abs( goal - l_sum - r_sums[index] ) )
                # print( l_sum, r_sums[index], goal )

            # not too far left
            if index > 0:
                result = min( result, abs( goal - l_sum - r_sums[index-1] ) )
                # print( l_sum, r_sums[index-1], goal )

        return result
205000