<p>You are given an integer <code>n</code> representing the length of an unknown array that you are trying to recover. You are also given an array <code>sums</code> containing the values of all <code>2<sup>n</sup></code> <strong>subset sums</strong> of the unknown array (in no particular order).</p>

<p>Return <em>the array </em><code>ans</code><em> of length </em><code>n</code><em> representing the unknown array. If <strong>multiple</strong> answers exist, return <strong>any</strong> of them</em>.</p>

<p>An array <code>sub</code> is a <strong>subset</strong> of an array <code>arr</code> if <code>sub</code> can be obtained from <code>arr</code> by deleting some (possibly zero or all) elements of <code>arr</code>. The sum of the elements in <code>sub</code> is one possible <strong>subset sum</strong> of <code>arr</code>. The sum of an empty array is considered to be <code>0</code>.</p>

<p><strong>Note:</strong> Test cases are generated such that there will <strong>always</strong> be at least one correct answer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, sums = [-3,-2,-1,0,0,1,2,3]
<strong>Output:</strong> [1,2,-3]
<strong>Explanation: </strong>[1,2,-3] is able to achieve the given subset sums:
- []: sum is 0
- [1]: sum is 1
- [2]: sum is 2
- [1,2]: sum is 3
- [-3]: sum is -3
- [1,-3]: sum is -2
- [2,-3]: sum is -1
- [1,2,-3]: sum is 0
Note that any permutation of [1,2,-3] and also any permutation of [-1,-2,3] will also be accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, sums = [0,0,0,0]
<strong>Output:</strong> [0,0]
<strong>Explanation:</strong> The only correct answer is [0,0].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
<strong>Output:</strong> [0,-1,4,5]
<strong>Explanation:</strong> [0,-1,4,5] is able to achieve the given subset sums.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
	<li><code>sums.length == 2<sup>n</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= sums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def recoverArray(self, k: int, sums: List[int]) -> List[int]:
        # we're given all 2**n subset sums in  NO PARTICULAR ORDER

        # values in the original array can be negative

        # the most negative entry is the sum of all negatives
        # the most positive entry is the sum of all positives

        # so that bounds the min and max value, and all sums are in -1e4..1e4 so that does help us

        # b1*n1 + ... bn*nn

        # we have ALL subset sums
        # so suppose we start with the sum of all numbers: sum of all positive and all negative => most positive + most negative
        
        # then if we discard a positive element the sum goes down
        #                      negative element the sum goes up

        # so the smallest deviations in each direction give us the smallest positive and negative
        #   ... except no, if we have x and -(x-1) then the smallest deviation can be dropping x and -(x-1) for -1
        #   and we'd conclude that blah blah blah...

        #### NEW APPROACH: DFS + BT?

        # Tried this, it was complicated to get early pruning right
        #  top of call: dfs(P, N, p, n, curr)
        #     P, N remaining sum of positive and negative needed
        #     p, n are values remaining in the valid range; try P..1 and N..-1 so we don't retry things we've already tried
        #     curr are the current bits
        #
        # problem: adding a negative value down-shifts positive combos and upshifts negative ones, ugh

        # max subset sum: all posities, no negatives -> get sum of positives
        # min subset sum: ... -> sum of negatives
        #
        #    suppose v is a value. then we can form 0 and v. Then we continue
        #    with trying to form the rest of the subset sums given we can make 0 and v
        #  if we pick the max possible positive then any positive we pick thereon will exceed the max -> discard it
        # so tracking the max remaining positive and negative seems like a good idea

        # suppose we can form sums {curr} so far
        # e.g. 0, -3
        # then we consider -1
        # we can form 0,-3   and -1, -4    // the downshift issue
        # not too bad though because
        #    tracking remaining N, sum of negatives, means we don't downshift past the minimum possible
        
        # P = max(sums)
        # N = min(sums)

        # target = 0
        # for s in sums:
        #     target |= 1 << (s - N)

        # lo = N # so we remember original N in the dfs code

        # picked = []
        # def dfs(P, N, p, n, curr) -> bool:
        #     if curr == target:
        #         return True

        #     r = k - len(picked)
        #     if p*r < P or r*n > N: return False

        #     # pick the positives first
        #     for v in range(p, 0, -1):
        #         if not (target & (1 << (v-lo))): continue # should show up by itself among all subset sums
        #         with_v = curr | (curr << v)
        #         diffs = with_v ^ target # where with_v and target differ: 1 in with_v and 0 in target (bad) or vice-versa (okay)
        #         okay_diffs = diffs & target # where there's a 0 in with_v, and a 1 in target
        #         if diffs == okay_diffs:
        #             # no sums in with_v that are not in target: this is a candidate
        #             picked.append(v)
        #             if dfs(P-v, N, min(P-v, v), n, with_v): return True
        #             picked.pop()

        #     if P: return False # need to pick positives, but none of them worked

        #     for v in range(n, 0):
        #         if not (target & (1 << (v-lo))): continue
        #         with_v = curr | (curr >> (-v)) # negative values reduce sums: a left shift
        #         diffs = with_v ^ target
        #         okay_diffs = diffs & target
        #         if diffs == okay_diffs:
        #             picked.append(v)
        #             if dfs(0, N-v, 0, max(N-v, v), with_v): return True
        #             picked.pop()

        #     if N: return False

        # dfs(P, N, P, N, 1 << (0-N))

        # picked.extend(0 for _ in range(k-len(picked))) # fill with zeros

        # return picked



        ### hokay, as expected that gives TLE

        # so now what?
        
        # maybe a different approach

        # suppose we look at all subsets with some value v and without
        #   {without} | {without+v} are the total ones

        # if for every without sum w there's a w+v then v is plausibly in the collection

        # so we can count frequencies of sums in order, the max is with v > 0
        #    if we see max and max-v then decrement both

        # that would mean iterating over 2**n for each of the positive values in general until we find an acceptable one

        # that's 65k ish for each value, too expensive

        # ASDF FOO BAR

        # I give up, solutions time


        # DBabichev to the rescue once again
        
        # sort the subsets and look at the difference of nums[0] and nums[1]

        # suppose we start with N, the sum of all negative numbers

        # then we look at nums[1], the smallest change
        #     we can lose a negative number, which increases the sum
        #     or we can take a positive, which increases the sum
        # so the smallest change is one or the other
        
        # GAH duh, I was thinking "smallest difference" which was long the right lines, but it's FIRST difference that matters!

        # wait... what do we do after taking x?
        #   > answer: use my other insight which is that if x is valid, then we can split subsets into
        #     with_x and without_x

        counts = Counter(sums)
        uniques = list(counts.keys())
        uniques.sort()

        picked = []
        def dfs(counts: Counter, uniques: list[int]) -> bool:
            """
            Returnst rue if picked[:] plus remaining picks can create `sums`. Otherwise returns False.

            Appends elements to `picked` if this returns True.
            """

            if len(uniques) == 1: return True

            d = uniques[1] - uniques[0]
            # per logic above the delta is either +d or -d

            for d in [d, -d]:
                if d not in counts: continue

                rem = Counter(counts) # clone counts
                without = Counter()

                if d < 0:
                    it = iter(uniques)
                else:
                    it = reversed(uniques)
                
                for u in it:
                    if rem[u] == 0: continue # copies of u already accounted for
                    if rem.get(u-d, 0) < rem[u]: break # not enough copies, d can't be right
                    rem[u-d] -= rem[u]
                    without[u-d] = rem[u]
                else:
                    # didn't break
                    uniques_without = list(without.keys())
                    if d > 0:
                        # processed u in reverse so the dictionary is reversed (Python dicts remember insert order)
                        # and thus we need to reverse uniques_without
                        uniques_without.reverse()

                    picked.append(d)
                    if dfs(without, uniques_without): return True
                    picked.pop()

            return False

        dfs(counts, uniques)

        picked.extend(0 for _ in range(k-len(picked)))

        return picked
903