从所有子集恢复原始阵列
你会得到一个数组的所有子集和。然后，您应该从提供的子集和中恢复原始数组。
保证原始数组中的每个元素都是非负数且小于10^5。原始数组中的元素不超过20个。原始数组也会被排序。保证输入是有效的。
示例1
如果提供的子集和如下所示：
0 1 5 6 6 7 11 12我们可以快速推断出原始数组的大小为3，因为有8 (2^3)个子集。上述输入的输出(即原始数组)如下所示：
1 5 6示例2
输入：
0 1 1 2 8 9 9 10输出：
1 1 8我尝试了什么
由于保证所有元素都是非负的，因此输入中的最大整数必须是数组的总和。然而，我不确定我该如何从那里开始。从逻辑上讲，我认为下一个(2^2 - 1)个最大的子集和必须包括数组中除一个元素之外的所有元素。
但是，当原始数组为以下数组时，上述逻辑不起作用：
1 1 8这就是为什么我被困住了，不知道如何继续下去。
回答 2
Stack Overflow用户
发布于 2018-06-03 14:22:44
假设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的Si可以是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个元素。
Stack Overflow用户
发布于 2018-06-05 06:23:49
这里有一个简单的算法，不需要找出哪个子集和给定的数字。
S←输入序列
X←空序列
而S有一个非零元素：
- d当S不为空时，
- Insert d in X
- N
empty sequence
- in X
- N
empty sequence
- ：H19z←S的最小元素H111从S中删除z和z+d (如果S不包含z+d，则是错误的；如果several).
- Insert z在N.
中，则仅删除z和z+d的一个实例
- S
N←
输出X。
https://stackoverflow.com/questions/50663548
复制相似问题
腾讯云开发者
