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

        # O(2^(N/2))
        def generate_sums(i, arr, curr, res):
            if i == len(arr):
                res.append(sum(curr))
                return
            curr.append(arr[i])
            generate_sums(i + 1, arr, curr, res)
            curr.pop()
            generate_sums(i + 1, arr, curr, res)
        
        N = len(nums)
        right_arr = nums[: N//2]
        left_arr = nums[N//2:]

        right_sums = []
        left_sums = []

        generate_sums(0, right_arr, [], right_sums)
        generate_sums(0, left_arr, [], left_sums)

        # O(2^(N/2) log (2^(N/2))) = O(2^(N/2) * N/2)
        right_sums.sort()

        # O(log 2^(N/2)) = O(N/2)
        def find_ind(i):
            # target is what we want to look for in the right sums array
            # to get as close as possible to goal num
            target = goal - left_sums[i]
            # binary search to find value in right_sums arr
            l, r = 0, len(right_sums) - 1
            min_diff = float("inf")
            while l <= r:
                m = (l + r) // 2
                # min_diff = min(min_diff, abs(target - right_sums[m]))

                if target == right_sums[m]:
                    return m
                elif target > right_sums[m]:
                    l = m + 1
                else:
                     r = m - 1
            
            return l
        
        # O(2^(N/2) * log(2^(N/2))) = O(2^(N/2) * N/2) = O(2^(N/2) * N) 
        res = float("inf")
        for i in range(len(left_sums)):
            ind = find_ind(i)
            if ind < len(right_sums):
                res = min(res, abs(goal - (left_sums[i] + right_sums[ind])))
            if ind > 0:
                res = min(res, abs(goal - (left_sums[i] + right_sums[ind - 1])))
        
        return res       
        
104700