Find Array Given Subset Sums — LeetCode 1982 Python Solution
HardArrayDivide and Conquer
- Problem
- #1982
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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).
Example
- 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:
Python solution
Python
class Solution:
def recoverArray(self, n: int, sums: List[int]) -> List[int]:
m = -min(sums)
sl = SortedList(x + m for x in sums)
sl.remove(0)
ans = [sl[0]]
for i in range(1, n):
for j in range(1 << i):
if j >> (i - 1) & 1:
s = sum(ans[k] for k in range(i) if j >> k & 1)
sl.remove(s)
ans.append(sl[0])
for i in range(1 << n):
s = sum(ans[j] for j in range(n) if i >> j & 1)
if s == m:
for j in range(n):
if i >> j & 1:
ans[j] *= -1
break
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n log n) (typical) |
| Space | O(log n) auxiliary |
Related problems
Frequently asked questions
- How hard is LeetCode 1982. Find Array Given Subset Sums?
- LeetCode 1982. Find Array Given Subset Sums is rated Hard on LeetCode.
- What topics does LeetCode 1982. Find Array Given Subset Sums cover?
- LeetCode 1982. Find Array Given Subset Sums is tagged Array and Divide and Conquer on LeetCode.