Description
You are given an integer array sums containing all 2^n subset sums of an unknown array of n integers. Reconstruct and return any valid original array.
Examples
Input:
n = 3, sums = [-3,-2,-1,0,0,1,2,3]Output:
[1,2,-3]Explanation:
One valid array.
Input:
n = 2, sums = [-1,2,4,5]Output:
[3,-1]Explanation:
The array [3,-1] produces subset sums: {} = 0, {-1} = -1, {3} = 3, {3,-1} = 2. The given sums [-1,2,4,5] encode these values with an offset.
Input:
n = 1, sums = [0,5]Output:
[5]Explanation:
For n=1, there are 2^1 = 2 subset sums. The subsets are: empty set {} with sum 0, and {5} with sum 5. Therefore, the original array contains exactly one element: 5.
Constraints
- •
1 ≤ n ≤ 15