<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:
        # Intution:
        # 1. Split the array into two halves
        # 2. Create two arrays - left sum and right sum and store all combination of left sum with size of left sum array and the same with right sum array. Because incase of odd number of elements in the array one array will contain more elements than the other
        # 3. Iterate over all the elements on the left and binary search and find the closest element -> Target - leftsum[i] to find the minimum difference
        # When goal 0 we can just choose no elements 
        if goal == 0: 
            return 0

        n = len(nums)
        mid = n // 2
        # Split the list in 2 parts and then find all possible subset sums 
        # T = O(2^n/2) to build all subset sums
        leftList = nums[:mid]
        leftSums = []
        rightList = nums[mid:]
        rightSums = []

        # T = O(2^n/2) to build all subset sums (we only consider half list)
        def buildSubsetSums(usedNums, numsToChooseFrom, ind, storeIn):
            if ind == len(numsToChooseFrom):
                # We also keep elements with sum 0 to deal with cases like this where we don't select nums
                # List: [1,2,3], Target: -7 (choosing no elements will give a sum close to goal)
                # We can also have cases where we want to take only 1 element from the list
                # so sum 0 for left and right list needs to be an option
                storeIn.append(sum(usedNums))
                return 

            usedNums.append(numsToChooseFrom[ind])
            buildSubsetSums(usedNums, numsToChooseFrom, ind+1, storeIn)
            usedNums.pop()
            buildSubsetSums(usedNums, numsToChooseFrom, ind+1, storeIn)


        # Calculates sums of all subarrays and stores it here
        buildSubsetSums([], leftList, 0, leftSums)
        buildSubsetSums([], rightList, 0, rightSums)
        # 2^n/2 log(2^n/2) = n/2 * 2^n/2 time to sort
        rightSums.sort()

        diff = float('inf')

        # Loop runs 2^n/2 times and inside binary search tale n/2 time 
        # So total time is n/2 * 2^n/2
        for leftSum in leftSums:
            complement = goal - leftSum
            # Bisect left takes log(2^n/2) = n/2 search time
            idx = bisect.bisect_left(rightSums, complement)

            for i in [idx - 1, idx, idx + 1]:
                if 0 <= i < len(rightSums):
                    finalSum = leftSum + rightSums[i]
                    diff = min(diff, abs(goal - finalSum))
        
        # Over all time complexity is - n/2 * 2^n/2
        # 1. Making subset sums will take - 2^n/2
        # 2. Sorting right list takes - 2^n/2 * n/2
        # 3. Iterating one list and finding closest complement in other 
        # takes n/2 * 2^n/2
        # Space will be O(n/2) for the list and call stack for building subset 
        return diff

104500