从子集的和还原数组

难度: Hard

存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2ⁿ 个 子集的和 组成（子集中的元素没有特定的顺序）。

返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在多种答案，只需返回其中 任意一个 。

如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个子集。sub 的元素之和就是 arr 的一个 子集的和 。一个空数组的元素之和为 0 。

注意：生成的测试用例将保证至少存在一个正确答案。

示例 1：

输入：n = 3, sums = [-3,-2,-1,0,0,1,2,3]
输出：[1,2,-3]
解释：[1,2,-3] 能够满足给出的子集的和：
- []：和是 0
- [1]：和是 1
- [2]：和是 2
- [1,2]：和是 3
- [-3]：和是 -3
- [1,-3]：和是 -2
- [2,-3]：和是 -1
- [1,2,-3]：和是 0
注意，[1,2,-3] 的任何排列和 [-1,-2,3] 的任何排列都会被视作正确答案。

示例 2：

输入：n = 2, sums = [0,0,0,0]
输出：[0,0]
解释：唯一的正确答案是 [0,0] 。

示例 3：

输入：n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
输出：[0,-1,4,5]
解释：[0,-1,4,5] 能够满足给出的子集的和。

提示：

1 <= n <= 15
sums.length == 2ⁿ
-10⁴ <= sums[i] <= 10⁴

Submission

运行时间: 268 ms

内存: 21.3 MB

class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        def base(s: List[int]):
            if len(s) == 1:
                return [0]
            diff = s[1] - s[0]
            rec, s1, s2 = deque(), [], []
            for x in s:
                if rec and rec[0] == x - diff:
                    s1.append(x - diff)
                    s2.append(x)
                    rec.popleft()
                else:
                    rec.append(x)
            if diff in s and (r := base(s1)):
                return r + [diff]
            if -diff in s and (r := base(s2)):
                return r + [-diff]
            return []
        return base(sorted(sums))[1:]

Explain

该题解使用递归与分治的方法来还原未知数组。首先对给定的子集和数组'sums'进行排序，以便于寻找可能的子集差异。递归函数'base'通过不断地寻找可能的子集差异来逐步还原原数组。每次递归中，计算可能的元素'diff'为两个连续元素的差值。然后尝试将'sums'中的元素分成两个子集's1'和's2'，其中一个包含'diff'，另一个不包含。这通过检查是否存在一个与'diff'匹配的元素来完成。若成功分组，则继续递归直到恢复出所有原始元素或确认当前路径不可能（通过检查'diff'的存在性）。最终，'base'函数返回包含原数组元素的列表。由于函数最初返回的数组包含了一个额外的0元素（代表空子集的情形），因此在最后的返回时忽略第一个元素。

时间复杂度: O(n * 2^n)

空间复杂度: O(n * 2^n)

class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        def base(s: List[int]):
            if len(s) == 1: # 如果数组长度为1，说明已经到达底部，返回[0]
                return [0]
            diff = s[1] - s[0] # 计算可能的差值
            rec, s1, s2 = deque(), [], [] # 初始化两个子集和一个队列用于记录
            for x in s: # 遍历当前的'sums'
                if rec and rec[0] == x - diff: # 检查队列的首元素是否与当前元素和diff的差相等
                    s1.append(x - diff) # 将调整后的元素添加到s1
                    s2.append(x) # 将当前元素添加到s2
                    rec.popleft() # 从队列中移除元素
                else:
                    rec.append(x) # 否则将元素添加到队列
            if diff in s and (r := base(s1)): # 如果'diff'存在于'sums'且递归调用返回非空结果
                return r + [diff] # 返回包含'diff'的结果
            if -diff in s and (r := base(s2)): # 如果'-diff'存在于'sums'且递归调用返回非空结果
                return r + [-diff] # 返回包含'-diff'的结果
            return [] # 如果上述条件都不满足，返回空数组
        return base(sorted(sums))[1:] # 忽略返回数组的第一个元素

Explore

在题解中，递归函数 'base' 通过使用一个双端队列 'rec' 来追踪已处理和未处理的元素，确保可以正确地将 'sums' 分成包含 'diff' 和不包含 'diff' 的两个子集。函数通过计算两个连续元素的差值 'diff'，然后遍历 'sums' 中的每个元素，检查这个元素减去 'diff' 后是否已存在于队列中。如果存在，则说明该元素与队列中的某个元素共同构成了包含 'diff' 的子集；否则，该元素可能属于不包含 'diff' 的子集。这种方法允许函数在每次递归调用中准确地分组，进而逐步还原原数组。

当 'sums' 数组的长度为1时，返回 [0] 并不意味着原始数组中必定包含元素0。这一步骤实际上是表示在该递归路径下，已经处理完所有可能的元素差异，并且剩下的唯一子集和是由空集产生的0。这是一个基础情况，用于递归算法的终止条件。因此，这种做法主要是为了处理递归过程中达到最小可能子集的情况，并不直接反映原始数组的内容。

在题解中使用双端队列 'rec' 而不是普通列表的主要优势在于其高效的元素插入和删除操作。特别是在需要频繁地在队列的前端添加或移除元素的场景下，双端队列提供了更优的性能。在普通列表中，这些操作通常具有线性时间复杂度，而在双端队列中，它们的时间复杂度为常数。这使得在递归过程中，对元素的动态增减更加高效，从而提升整体算法的性能。

考虑 'diff' 和 '-diff' 的存在性是因为原数组中的元素可能包含正数和负数，这使得两个子集的和可能表现为原始元素的正负差异。在算法中检查 '-diff' 的存在性是为了处理这种可能性，确保可以正确地还原包含负数的原数组。如果原数组中的元素是正负对称的，那么任何一个正数元素的存在同样意味着其对应的负数元素可能存在，这样的处理确保了算法的正确性和完整性。