<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:
                # We can choose to include the num in the subsequence or dont include
        # But then again that is a brute force approach. Maybe improve using memoization? O(2^N)
        # The optimized solution is to apply the "Meet in the middle algorithm"

        # S1: Divide the array into 2 equal parts. Length of each array becomes N / 2
        # S2: Find all possible subsequence sums within the split arrays
        # S3: We have 2 options:
        # The first is 2 pointer approach. But if we play this out, the time complexity will be as bad as brute force because it involves fixing one value and iterating through the other array to find the sum closest
        # The second is to sort one of the arrays
        # The reason for sorting is so that we can apply binary search
        # [0, 5, 3, 8] and [-1, 0, 6, 7] (sorted)
        # x + y <= sum
        # y <= sum - x
        # Iterate through the first array (x) and find y
        # So e.g x = 5 then y = 13 - 5 = 8
        # We use bisect_left or binary search to find the largest number that is smaller than 8 which in the other array is 7
        # We then update our res variable
        # We will go with our second approach as the time complexity is more optimized
        def generate_sums(nums):
            # Time Complexity: O(2^(N / 2))
            """Generate all possible subsequence sums of the list nums."""
            sums = []
            for combination in chain.from_iterable(combinations(nums, r) for r in range(len(nums) + 1)):
                sums.append(sum(combination))
            return sums
        
        n = len(nums)

        # Split the array into 2 parts
        left_nums = nums[:n // 2] 
        right_nums = nums[n // 2:]
        
        # Generate all possible subsequence sums for each part
        # Length of left_sums and right_sums respectively are 2 ^ (N / 2)
        # Time Complexity = O(2 * (2 ^ (N / 2)))
        left_sums = generate_sums(left_nums)
        right_sums = generate_sums(right_nums)

        # Sort the nums of the second part for binary search
        # Time Complexity = O((2 ^ (N / 2)) log (2 ^ (N / 2))) = O((N / 2) * (2 ^ (N / 2)))
        right_sums.sort()

        res = float('inf')

        # Iterate through each sum in left_sums and find the closest sum in right_sums
        # Binary Search Time Complexity in this case will be on right_sums
        # So TC for Binary Search is O(log (2 ^ (N / 2))) = N / 2 becos of log base 2
        # Total Search Time will be length of left_sums * binary search
        # Hence Time Complexity = O((2 ^ (N / 2)) * N / 2)
        for sum1 in left_sums:
            target = goal - sum1
            idx = bisect_left(right_sums, target) # this finds the index of the largest value that is less than the target value

            # Check the closest sum greater than or equal to (goal - sum1)
            if idx < len(right_sums):
                res = min(res, abs(goal - (sum1 + right_sums[idx])))
            
            # Check the closest sum less than (goal - sum)
            if idx > 0:
                res = min(res, abs(goal - (sum1 + right_sums[idx - 1])))
        
        return res

        # Total Time Complexity of this algorithm is:
        # O(2 * (2 ^ (N / 2))) + O((N / 2) * (2 ^ (N / 2))) + O((N / 2) * (2 ^ (N / 2)))
        # O(N * (2 ^ (N / 2)))
110000