#1982
Find Array Given Subset Sums
candidate master · 1440 · lc hard +32 · failed · 49.6% accepted · 633 likes · top 37%
Description
An unknown array of length n has been hidden from you, but you are provided the array sums containing every one of its 2n possible subset sums in arbitrary order (the empty subset contributes 0).
Recover and return any valid array of length n whose subset sums match sums. A correct answer is guaranteed to exist.
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.
Code
1
2
3