从所有子集中恢复原始阵列 [英] Recover original array from all subsets

问题描述

将为您提供数组的所有子集和.然后，应该从提供的子集和中恢复原始数组.

You are given all subset sums of an array. You are then supposed to recover the original array from the subset sums provided.

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

Every element in the original array is guaranteed to be non-negative and less than 10^5. There are no more than 20 elements in the original array. The original array is also sorted. The input is guaranteed to be valid.

示例1

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

If the subset sums provided are this:

0 1 5 6 6 7 11 12

由于有8(2 ^ 3)个子集，我们可以快速推断出原始数组的大小为3.上面输入的输出(即原始数组)是这样的:

We can quickly deduce that the size of the original array is 3 since there are 8 (2^3) subsets. The output (i.e original array) for the above input is this:

1 5 6

示例2

输入:

0 1 1 2 8 9 9 10

输出:

1 1 8

我尝试过的事情

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

Since all elements are guaranteed to be non-negative, the largest integer in the input must be the total of the array. However, I am not sure as to how do I proceed from there. By logic, I thought that the next (2^2 - 1) largest subset sums must include all except one element from the array.

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

However, the above logic does not work when the original array is this:

1 1 8

这就是为什么我被困住并且不确定如何进行的原因.

That's why I am stuck and am not sure on how to proceed on.

推荐答案

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

Say S is the subset sum array and A is the original array. I'm assuming S is sorted.

|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达到合适的大小时停止.

In general, S[i] for i >= 3 is either an element of A or a combination of the elements of A that you've already encountered. When processing S, skip once per combination of known elements of A that generate a given number, add any remaining numbers to A. Stop when A gets to the right size.

例如，如果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，然后看到我们知道必须属于A的第三个9.

E.g., if A=[1,2,7,8,9] then S will include [1,2,1+2=3,...,1+8=9, 2+7=9,9,...]. When processing S we skip over two 9s because of 1+8 and 2+7, then see a third 9 which we know must belong to A.

例如，如果S = [0,1,1,2,8,9,9,10]，则我们知道A具有3个元素，当我们得到A的前两个元素为[1,1]到2，因为1 + 1 = 2，所以我们跳过它，我们追加8，就完成了，因为我们有3个元素.

E.g., if S=[0,1,1,2,8,9,9,10] then we know A has 3 elements, that the first 2 elements of A are [1,1], when we get to 2 we skip it because 1+1=2, we append 8 and we're done because we have 3 elements.

这篇关于从所有子集中恢复原始阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！