Find Array Given Subset Sums LeetCode solution in Python

1
# Runtime: 4011 ms (Top 18.39%) | Memory: 19.7 MB (Top 40.23%)
2
class Solution:
3
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
4
        res = []  # Result set
5
        sums.sort()
6

7
        while len(sums) > 1:
8
            num = sums[-1] - sums[-2]  # max - secondMax
9
            countMap = Counter(sums)  # Get count of each elements
10
            excluding = []  # Subset sums that do NOT contain num
11
            including = []  # Subset sums that contain num
12

13
            for x in sums:
14
                if countMap.get(x) > 0:
15
                    excluding.append(x)
16
                    including.append(x + num)
17
                    countMap[x] -= 1
18
                    countMap[x + num] -= 1
19

20
            # Check validity of excluding set
21
            if 0 in excluding:
22
                sums = excluding
23
                res.append(num)
24
            else:
25
                sums = including
26
                res.append(-1 * num)
27

28
        return res