LC 1982. 从子集的和还原数组

https://leetcode-cn.com/problems/find-array-given-subset-sums/

这题思路有三个步骤：

  1. 将整个数组拆分成为两个数组A, B. 每个元素的差x = A - B是相同的。
  2. 假设这个差x, 那么说明存在x或者是-x. 如果是x那么继续拆分B，如果是-x那么继续拆分A
  3. 必须保证拆分元素里面存在一个元素0

其中2，3这个我想到了，但是第1点有点卡住了，没有想到特别有效的办法来做数组拆分。

看了题解之后才知道有个非常有效的解法，选择数组中最小和次小的元素A, B. 那么x = A - B. 这个证明非常简单：

  1. 如果元素都是非负数，那么结果是显而易见的。
  2. 如果元素里面有负数，那么最小值就是所有负数的和
  3. 而第二小的数，是从最小值从删除一个最大的负数，或者是加上一个最小的正数。
class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        sums.sort()

        print(sums)

        def split(data):
            delta = data[1] - data[0]
            from collections import Counter
            used = Counter()
            total = Counter(data)

            left, right = [], []
            for i in range(len(data)):
                x = data[i]
                if used[x]:
                    used[x] -= 1
                    continue
                left.append(x)
                exp = delta + x
                total[exp] -= 1
                used[exp] += 1
                right.append(exp)

            return left, right, delta

        def search(data, ans):
            if len(data) == 1:
                return data[0] == 0

            left, right, exp = split(data)
            if 0 in left:
                ans.append(exp)
                if search(left, ans):
                    return True
                ans.pop()

            if 0 in right:
                ans.append(-exp)
                if search(right, ans):
                    return True
                ans.pop()
            return False

        ans = []
        ok = search(sums, ans)
        return ans