HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Recover a set with the information of the sums of all its subsets

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theallwithsubsetsrecoveritssumssetinformation

Problem

I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$?

I have $2^n $ data. This is far more than $n$, the number of unknowns.

Solution

No you can't. Consider any set $S=\{a,b,c\}$ with $a+b+c=0$, and the set $S'=\{a+b,b+c,c+a\}$.

The subset sums for $S$ are $0, a, b, c, a+b, b+c, c+a, a+b+c=0$.

The subset sums for $S'$ are $0, a+b, b+c, c+a, a+2b+c=b, b+2c+a=c, c+2a+b = a, 2(a+b+c)=0$.

Hence, you can't distinguish $S$ and $S'$ from the subset sums: $0, a, b, c, a+b, b+c, c+a, 0$.

If all elements are non-negative, then the smallest subset sums should respectively correspond to the empty set and the singletons made up of the smallest two elements, thus you can know the smallest two elements. Once you know the smallest $k$ elements, you can know the subset sums corresponding to the subsets made up of these $k$ elements. Extract them, then the smallest subset sum should correspond to the $(k+1)$-th smallest element. Repeat the process above, you will finally get all elements.

Context

StackExchange Computer Science Q#142862, answer score: 29

Revisions (0)

No revisions yet.