patternMajor
Recover a set with the information of the sums of all its subsets
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.
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.
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.