<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:
        def sums(arr):
            sums = {0}
            for a in arr:
                sums |= {s + a for s in sums}
            return sums        
        sums1 = sums(nums[1::2])
        s2 = sorted(sums(nums[::2]))

        ans=10**10
        # for each possible sum of the 1st half, find the sum in the 2nd half
        # that gives a value closest to the goal using binary search
        for s in sums1:
            remain=goal-s
			# binary search for the value in s2 that's closest to the remaining value
            i2=bisect_left(s2,remain)
            if i2<len(s2):
                ans=min(ans,abs(remain-s2[i2]))
            if i2>0:
                ans=min(ans,abs(remain-s2[i2-1]))
            if ans == 0 : return 0
        return ans

class MySolution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        # Method1: all possible sums of subarrays given an array
        def dfs(i, cur, arr, sums):
            if i == len(arr):
                sums.add(cur)
                return
            dfs(i+1, cur, arr, sums)
            dfs(i+1, cur+arr[i], arr, sums)
        #sums1, sums2 = set(), set()
        #dfs(0, 0, nums[0:len(nums)//2], sums1)
        #dfs(0, 0, nums[len(nums)//2:], sums2)

        # Method2: better. Uses self-inflating set of sums in for loop
        def sums(arr):
            sums = {0}
            for a in arr:
                sums |= {s + a for s in sums}
            return sums
        # takes every second element starting from 1 and 0
        sums1 = sums(nums[1::2])
        sums2 = sorted(sums(nums[::2]))

        result = sys.maxsize
        # need convert the set into a sorted list
        # don't put this in the loop
        sorted_list = sorted(sums2)
        for s in sums1:
            # we want to find in sums2 as close as to r
            r = goal - s            
            # find the index larger or equal to r
            i = bisect_left(sorted_list, r)
            if i < len(sorted_list):
                result = min(result, sorted_list[i] - r)
            if i > 0:
                result = min(result, abs(r - sorted_list[i-1]))
        return result

35900