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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 2 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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...

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9152297973632812, "perplexity_flag": "head"}