1982：从子集的和还原数组（2872 分）

2021-08-22 约 729 字预计阅读 2 分钟次阅读

力扣第 255 场周赛第 4 题

题目

存在一个未知数组需要你进行还原，给你一个整数 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⁴

相似问题：

分析

考虑 sums 的最大数 ma 和次大数 ma2，则要么 ma-ma2 在原数组中，要么 ma2-ma 在原数组中
假设 x 在原数组中，则可以将 sums 分为两部分，包含x的和不包含x的，不包含 x 的即是子问题，递归即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        def gen(A,x):
            ct = Counter(A)
            B,C = [],[]
            for a in A:
                if ct[a]:
                    ct[a] -= 1
                    ct[a+x] -= 1
                    if ct[a+x]<0:
                        return [],[]
                    B.append(a)
                    C.append(a+x)
            return B,C

        def dfs(A):
            if len(A)==2:
                if 0 not in A:
                    return []
                A.remove(0)
                return A
            x = A[-1]-A[-2]
            B,C = gen(A,x)
            if B:
                res = dfs(B)
                if res:
                    return [x]+res 
            if C:
                res = dfs(C)
                if res:
                    return [-x]+res
            return []
        sums.sort()
        return dfs(sums)

929 ms

目录

1982：从子集的和还原数组（2872 分）

题目

分析

解答