13
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ "I have $2^n$ data" -- but, importantly, you don't have $2^n$ equations (if all you have is the set of sums. Otherwise, the problem is trivial). $\endgroup$ Aug 2 at 22:52
26
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ what if all the $n$ numbers are positive? $\endgroup$
    – S. Kohn
    Aug 2 at 8:42
  • 2
    $\begingroup$ The final algorithm assumes that no subset sum is also one of the original elements. For example, the subset sums for $\{1,2,3\}$ would be $\{0,1,2,3,4,5,6\}$, from which your algorithm would return $\{1,2,4\}$ as the original set. If we allow duplicates in the subset-sums though (so there are always $2^n$ elements), I believe it should work. $\endgroup$ Aug 3 at 19:07
3
$\begingroup$

If you know the sums of all the two element subsets you can recover the elements unless $n$ is a power of $2$. See

$\endgroup$
2
  • 1
    $\begingroup$ This assumes you can distinguish the 2-element sums from other n-element sums. We clearly can't assume we know how many elements went into each sum, since the 1-element sums would just be the elements themselves. $\endgroup$ Aug 3 at 18:59
  • 1
    $\begingroup$ @BlueRaja-DannyPflughoeft Agreed. This theorem assumes you have only the two element sums, so there's nothing to distinguish. So it's is not an answer to the exact question asked. But often here the exact question asked is not exactly what the OP needs. I posted because it might turn out useful. $\endgroup$ Aug 3 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.