<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:
        # subSEQ of nums - any subset is allowed, so order doesn't matter

        # return the minimum |sum-goal|

        # up to 40 nums, huge range
        # so DFS + backtracking on nums can be good
        # but 2**40 is too expensive for brute force so we need to do some pruning

        N = len(nums)

        # simplify code so we can always work with goal >= 0
        if goal < 0:
            for i in range(N): nums[i] *= -1
            goal *= -1

        if (posSum := sum(n for n in nums if n > 0)) <= goal: return goal - posSum

        nums = [n for n in nums if n] # drop zeros which don't matter
        nums.sort(key=lambda n: abs(n), reverse=True)
        N = len(nums)

        # idea: two halves trick
        #   we can store all possible sums of the last half of the numbers
        #   then use DFS + backtracking on the first half
        latterSums = {0}
        for i in range(N//2):
            n = nums.pop()
            # all sums: skip n (existing latterSums)
            #           or take n (all existing, plus n)
            latterSums |= {s+n for s in latterSums}

        latterSums = list(latterSums)
        latterSums.sort() # so we can do binary search later
        L = len(latterSums)

        # reset N to just the heavy hitters in front
        # and record the max positive and negative change
        # we can get for early pruning
        N = len(nums)
        posSums = [0]*(N+1)
        negSums = [0]*(N+1)
        posSums[-1] = max(0, max(latterSums))
        negSums[-1] = min(0, min(latterSums))
        for i in range(N-1, -1, -1):
            negSums[i] = min(nums[i], 0) + negSums[i+1]
            posSums[i] = max(nums[i], 0) + posSums[i+1]

        # for pruning:
        #  > suppose our sum thus far is s
        #  > and remaining numbers max positive sum p, and negative sum n
        #     then if target is outside (s+n, s+p) then give up

        # -----------------goal---------------
        #             |            | <- current best abs
        #     (                            )
        #     s------->
        #      s+posSum[i] has to be able to get us closer to goal
        #      s+negSum[i]: similar idea, but from above instead of below

        # print(f"{nums=}, {goal=}")

        ans = [math.inf]
        def dfs(i: int, s: int) -> int:
            # print(f"{i=}, {s=}: {posSums[i]=}, {negSums[i]=}")

            # pruning: if s is too far from goal, don't bother
            if s + posSums[i] <= goal - ans[0]: return
            if s + negSums[i] >= goal + ans[0]: return

            if i == N: # N is now the size of "left" part, the heavy hitters
                # want s + ls as close to goal as possible for ls in latterSums
                # so ls as close to goal-s as possible
                k = bisect_left(latterSums, goal-s) # first index >=
                if k < L: ans[0] = min(ans[0], s+latterSums[k]-goal) # closest >=
                if k: ans[0] = min(ans[0], goal-s-latterSums[k-1]) # closest <
                return

            # the main meat: we can take or leave each heavy hitter

            dfs(i+1, s + nums[i]) # take
            dfs(i+1, s) # leave

        # one small call for me, one giant computation for LC
        dfs(0, 0)

        # dfs is side-effecting: it sets the best as it explores
        return ans[0]
33900