<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 sortedSums(self, nums: List[int]) -> List[int]:
        if len(nums)==0:
            return [0]
        if len(nums)==1:
            if nums[0] < 0:
                return [nums[0], 0]
            elif nums[0] > 0:
                return [0, nums[0]]
            else:
                return [0]
        ssums1 = self.sortedSums(nums[0:len(nums)//2])
        ssums2 = self.sortedSums(nums[len(nums)//2:])
        result =[]

        sums_array = [[ssums1[i] + ssums2[j] for j in range(len(ssums2))] for i in range(len(ssums1))]
        pq = [(sums_array[i][0], 0, i) for i in range(len(sums_array))]
        heapq.heapify(pq)
        while len(pq)>0:
            t = heapq.heappop(pq)
            if len(result)==0 or result[len(result)-1] < t[0]:
                result.append(t[0])
            if t[1] + 1<len(ssums2):
                heapq.heappush(pq, (sums_array[t[2]][t[1]+1], t[1]+1, t[2]))
        #print(result)
        return result
    def closestSum(self, nums1: List[int], nums2: List[int], goal: int):
        i = 0
        j = len(nums2)-1
        min_diff = abs(nums1[i]+nums2[j]-goal)

        while i<len(nums1) and j>=0:
            #print(str(i)+" "+str(j))
            print(min_diff)
            while  j>=0 and i<len(nums1) and (nums1[i]+nums2[j])>goal:
                #print("1")
                if abs(nums1[i]+nums2[j]-goal) < min_diff:
                    min_diff = abs(nums1[i]+nums2[j]-goal)
                    if min_diff==0:
                        return 0
                j-=1
            while i<len(nums1) and j>=0 and (nums1[i]+nums2[j])<=goal:
                #print("2")
                if abs(nums1[i]+nums2[j]-goal) < min_diff:
                    min_diff = abs(nums1[i]+nums2[j]-goal)
                    if min_diff==0:
                        return 0
                i+=1
        return min_diff

    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        ssum1 = self.sortedSums(nums[0:len(nums)//2])
        ssum2 = self.sortedSums(nums[len(nums)//2:])
        #print(ssum1)
        #print(ssum2)
        #return 0
        return self.closestSum(ssum1, ssum2, goal)
        
108600