从所有子集中恢复原始数组

给定一个数组的所有子集和。然后，您应该从提供的子集和中恢复原始数组。

原始数组中的每个元素都保证为非负且小于 10^5。原始数组中的元素不超过 20 个。原数组也已排序。保证输入有效。

实施例1

如果提供的子集总和是这样的：

0 1 5 6 6 7 11 12

我们可以快速推断出原始数组的大小为 3，因为有 8 (2^3) 个子集。上述输入的输出（即原始数组）是这样的：

1 5 6

实施例2

Input:

0 1 1 2 8 9 9 10

Output:

1 1 8

我尝试过的

由于所有元素都保证为非负数，因此输入中的最大整数必须是数组的总和。但是，我不确定如何从那里继续。按照逻辑，我认为下一个 (2^2 - 1) 最大子集总和必须包括数组中除一个元素之外的所有元素。

但是，当原始数组是这样时，上述逻辑不起作用：

1 1 8

这就是为什么我陷入困境并且不确定如何继续。

假设 S 是子集和数组，A 是原始数组。我假设 S 已排序。

|A| = log2(|S|)
S[0] = 0
S[1] = A[0]
S[2] = A[1]
S[3] = EITHER A[2] OR A[0] + A[1].

一般来说，i >= 3 的 S[i] 要么是 A 的一个元素，要么是您已经遇到的 A 元素的组合。处理 S 时，对生成给定数字的 A 的已知元素的每个组合跳过一次，将任何剩余数字添加到 A。当 A 达到正确的大小时停止。

例如，如果 A=[1,2,7,8,9]，则 S 将包括 [1,2,1+2=3,...,1+8=9, 2+7=9,9,。 ..]。在处理 S 时，由于 1+8 和 2+7，我们跳过了两个 9，然后看到第三个 9，我们知道它一定属于 A。

例如，如果 S=[0,1,1,2,8,9,9,10] 那么我们知道 A 有 3 个元素，A 的前 2 个元素是 [1,1]，当我们达到 2 时，我们跳过它，因为 1+1=2，我们追加 8，我们就完成了，因为我们有 3 个元素。