Find the maximum set whose subset sum is unique for every of its subset.

Question

We are given a set of $n$ positive integers. We assume all of them are bounded by a polynomial of $n$. We would like to find a subset $S$ of numbers such that for any $T_1,T_2\subseteq S$, the sum of numbers in $T_1$ is not equal to that of $T_2$. We want the size of $S$ is maximized. Clearly, the problem is in NP and can be solved in $n^{O(\log n)}$ time (Since $|S|\leq O(\log n)$). Is this problem polynomial time solvable? Is this problem studied before? Any help is appreciated.

Answer 1

In the modern language, sets with all subset sums pairwise distinct are often called dissociated. Maximal dissociated subsets of a given set are important in Additive Combinatorics and Fourier analysis, although I cannot recall anybody ever addressing the algorithmic aspect.

Yet another reference you may find useful: http://math.haifa.ac.il/~seva/Papers/DisBases.pdf.

---

Added: taking into account the interpretation of a maximal dissociated subset of a given set $A$ as a "basis of $A$ over the set $\{-1,0,1\}$", it may be reasonable to try and adjust one of the standard algorithms of finding a maximal independent subset of a given set in a vector space.

Answer 2

This has been studied, see

http://www.mathnet.or.kr/mathnet/kms_tex/978590.pdf

and the somewhat more interesting:

NEWMAN POLYNOMIALS WITH PRESCRIBED VANISHING AND INTEGER SETS WITH DISTINCT SUBSET SUMS PETER BORWEIN AND MICHAEL J. MOSSINGHOFF

(available online)

See also the references in:

http://garden.irmacs.sfu.ca/?q=op/sets_with_distinct_subset_sums

None of these answers your question, but I think this is the state of the art...