你会得到一个数组的所有子集和。然后,您应该从提供的子集和中恢复原始数组。
保证原始数组中的每个元素都是非负数且小于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
这就是为什么我被困住了,不知道如何继续下去。
发布于 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个元素。
发布于 2018-06-05 06:23:49
这里有一个简单的算法,不需要找出哪个子集和给定的数字。
S←输入序列
X←空序列
而S有一个非零元素:
empty sequence
empty sequence
中,则仅删除z和z+d的一个实例
N←
输出X。
https://stackoverflow.com/questions/50663548
复制相似问题