subset sum

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $S \subseteq {\mathbb Z}$ has distinct subset sums if distinct subsets of $S$ have distinct sums.

Conjecture There exists a fixed constant $c$ so that $|S| \le \log_2(n) + c$ whenever $S \subseteq \{1,2,\ldots,n\}$ has distinct subset sums.

Posted by mdevos
updated April 7th, 2011