Formatted question description: https://leetcode.ca/all/1982.html

# 1982. Find Array Given Subset Sums

## Level

Hard

## Description

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 `2^n`

**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.

**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

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.

**Constraints:**

`1 <= n <= 15`

`sums.length == 2^n`

`-10^4 <= sums[i] <= 10^4`

## Solution

The minimum element in `sums`

is the sum of all negative elements in the original array, and the difference between the second minimum element in `sums`

and the minimum element in `sums`

is the minimum absolute value among all elements in the original array. Use `minNum`

to represent the element with the minimum absolute value. Divide `sums`

into two parts such that one part is the result of adding `minNum`

to each element in the other part. Repeat `n`

times to recover the original array.

```
class Solution {
public int[] recoverArray(int n, int[] sums) {
int total = 0;
for (int num : sums)
total += num;
int sum = total / (1 << n - 1);
Arrays.sort(sums);
int[] arr = new int[n];
List<Integer> sumsList = new ArrayList<Integer>();
for (int num : sums)
sumsList.add(num);
List<Integer> small = new ArrayList<Integer>();
List<Integer> large = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
int size = sumsList.size();
boolean[] selected = new boolean[size];
int minNum = sumsList.get(1) - sumsList.get(0);
boolean flag = false;
for (int j = 0; j < size; j++) {
if (!selected[j]) {
selected[j] = true;
small.add(sumsList.get(j));
for (int k = j + 1; k < size; k++) {
if (!selected[k] && sumsList.get(k) == sumsList.get(j) + minNum) {
selected[k] = true;
large.add(sumsList.get(k));
if (minNum == sumsList.get(k))
flag = true;
break;
}
}
}
}
sumsList.clear();
if (flag)
sumsList = new ArrayList<Integer>(small);
else {
sumsList = new ArrayList<Integer>(large);
minNum = -minNum;
}
small.clear();
large.clear();
arr[i] = minNum;
}
return arr;
}
}
```