HardNo. 1982
Find Array Given Subset Sums — LeetCode 1982 Python Solution
- Topics
- Array, Divide and Conquer
- 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
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
- Time
- O(n log n)(typical)
- Space · auxiliary
- O(log n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
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.