<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:
    # Generate the power set. Gather the sum of all the subsets in this and return
    def get_subset_sums(self, A: List[int]):
        result = set()
        n = len(A)
        limit = (1 << n)
        # Going through all the combinations generated
        for msk in range(limit):
            s = 0
            # Going through the length of the array
            for j in range(0, n):
                # Check if the i'th bit is set, to choose the element from the array
                if msk & (1 << j):
                    s += A[j]
            result.add(s)
        return result

    def get_subset_sums2(self, nums: List[int]):
	    ans = {0}
	    for x in nums: 
		    ans |= {x + y for y in ans}
	    return list(ans) 

    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        half_len = len(nums) // 2
        s1, s2 = self.get_subset_sums2(nums[:half_len]), self.get_subset_sums2(nums[half_len:])
        s2.sort() # doesn't work without sorting, because of bisect_left

        answer = math.inf
        
        for s in s1:
            remain = goal - s
            i2 = bisect_left(s2, remain)

            if i2 < len(s2):
                answer = min(answer, abs(remain - s2[i2]))
            if i2 > 0:
                answer = min(answer, abs(remain - s2[i2 - 1]))
                
        return answer

        
154400