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

Return the array ans of length n representing the unknown array. If multiple answers exist, return any of them.

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

Note: Test cases are generated such that there will always be at least one correct answer.

&nbsp;
Example 1:

Input: n = 3, sums = [-3,-2,-1,0,0,1,2,3]
Output: [1,2,-3]
Explanation: [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.


Example 2:

Input: n = 2, sums = [0,0,0,0]
Output: [0,0]
Explanation: The only correct answer is [0,0].


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 15
	sums.length == 2n
	-104 &lt;= sums[i] &lt;= 104


class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        res = [] # Result set
        sums.sort()

        while len(sums) > 1:
            num = sums[-1] - sums[-2] # max - secondMax
            countMap = Counter(sums) # Get count of each elements
            excluding = [] # Subset sums that do NOT contain num
            including = [] # Subset sums that contain num

            for x in sums:
                if countMap.get(x) > 0:
                    excluding.append(x)
                    including.append(x+num)
                    countMap[x] -= 1
                    countMap[x+num] -= 1

            # Check validity of excluding set
            if 0 in excluding:
                sums = excluding
                res.append(num)
            else:
                sums = including
                res.append(-1*num)

        return res
class Solution {
    public int[] recoverArray(int n, int[] sums) {
        Arrays.sort(sums);
        int m = sums.length;
        int[] res = new int[n], left = new int[m / 2], right = new int[m / 2];
        for (int i = 0; i < n; ++i) {
            int diff = sums[1] - sums[0], hasZero = 0, p = -1, q = -1, k = 0;
            for (int j = 0; j < m; ++j) {
                if (k <= q && right[k] == sums[j]) k++;
                else {
                    if (0 == sums[j]) hasZero = 1;
                    left[++p] = sums[j];
                    right[++q] = sums[j] + diff;
                }
            }
            if (1 == hasZero) {
                res[i] = diff;
                sums = left;
            } else {
                res[i] = -diff;
                sums = right;
            }
            m /= 2;
        }
        return res;
    }
}
class Solution {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        sort(sums.begin(), sums.end());

        vector<int> ans;
        while (n--) {
            int diff = sums[1] - sums[0];
            unordered_map<int, int> freq;
            vector<int> ss0, ss1;
            bool on = false;
            for (auto& x : sums)
                if (!freq[x]) {
                    ss0.push_back(x);
                    freq[x+diff]++;
                    if (x == 0) on = true;
                } else {
                    ss1.push_back(x);
                    freq[x]--;
                }
            if (on) {
                ans.push_back(diff);
                sums = ss0;
            } else {
                ans.push_back(-diff);
                sums = ss1;
            }
        }
        return ans;
    }
};
/**
 * @param {number} n
 * @param {number[]} sums
 * @return {number[]}
 */
var recoverArray = function(n, sums) {
    sums.sort((a, b) => a - b);
    let result = [];
    
    while (sums.length > 1) {
        let num = sums[sums.length - 1] - sums[sums.length - 2],
            excluding = [],
            including = [],
            counter = new Map();
        for (let item of sums) {
            let count = counter.get(item);
            if (count) {
                counter.set(item, count + 1);
            } else {
                counter.set(item, 1);
            }
        }
        
        for (let item of sums) {
            if (counter.get(item) > 0) {
                excluding.push(item);
                including.push(item + num);
                counter.set(item, counter.get(item) - 1);
                counter.set(item + num, counter.get(item + num) - 1);
            }
        }
        
        if (excluding.indexOf(0) !== -1) {
            sums = excluding;
            result.push(num);
        } else {
            sums = including;
            result.push(-1 * num);
        }
    }
    
    return result;
};
Find Array Given Subset Sums