正在恢复数组

Question

我最近在招聘挑战中遇到了这个问题：

给出数组S的2 ^ N个整数（1 <= N <= 20，0 <= Si <= 10 ^ 9），它们表示数组A的子集和，我们需要按排序的顺序恢复数组A。

例如S = {2，1，0，3} => A = {1，2}，因为A的子集和为{0，1，2，1 + 2}

数组S中的数字顺序可以是随机的。

我该如何解决这个问题？预先感谢。

Answer 1

您可以对包含子集和的数组进行排序当您对子集和数组进行排序时A i = S [2 ^ i]-应该按排序顺序给您数组A的值。

您可以制作一个真值表以获取子集总和并进行追溯假设S是有效输入例如：S = {0，5，3，8，1，6，4，9}

Sorted S = {0, 1, 3, 4, 5, 6, 8, 9} 
A = [A0, A1, A2] --- 

A0,A1,A2 -- (Binary, part of subset = 1 not part = 0 )

Index |  A0,A1,A2  | Sorted Sum  
0        0 0 0        0
1        1 0 0        1
2        0 1 0        3 
3        1 1 0        4 
4        0 0 1        5
5        1 0 1        6
6        0 1 1        8
7        1 1 1        9

From her we can reverse and find that A0 = S[2^0], A1 = S[2^1], A2 = S[2^2]