# Subset sum problem with at most one solution for any target

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there.

We first consider the search version of the subset sum problem: Given a set $$S$$ of $$n$$ naturals, find a subset of $$S$$ that sums to exactly $$W$$. My question concerns this problem, with an additional restriction on set $$S$$: For all possible values of $$X$$, there exists at most one subset that sums to $$X$$ (in other words, no two subsets of $$S$$ sum to the same value). Can we find a polynomial time algorithm for this problem given this restriction?

My thoughts: The reason I think this may be possible is because this is an extremely strong restriction on $$S$$. Most sets are very far from having this property. The construction of an algorithm would likely begin with a strong characterization of the sets that even have this property, and work from there. However, I'm having trouble proving strong theorems about the sets that obey this restriction.

• Just to clarify, you want the set S to have the uniqueness property for all possible values of X or just for W? – Konstantinos Koiliaris Mar 9 at 18:23
• @KonstantinosKoiliaris all possible values of $X$. This is also the reason that a reduction to unique SAT probably won't work (as was discussed in the CS.se thread) – DreamConspiracy Mar 9 at 18:30
• @KonstantinosKoiliaris yes. I'm not even convinced that we can't show this to be trivially polytime by arguing that $S$ has to be so sparse that traditional algorithms (DP) work. I haven't been able to find any literature about the asymptotic maximum size of $S$ given $W$ though. But maybe I'm just searching for the wrong thing. – DreamConspiracy Mar 9 at 19:12
• After a little bit of search: the property of $S$ is called subset-sum distinctness (see for example: Integer Sets with Distinct Subset-Sums or A generalization of a subset-sum-distinct sequence). There is also a conjecture by Conway-Guy. But I didn't find anything related to subset-sum. – Marzio De Biasi Mar 12 at 11:23
• This is kind of tangential, but the paper Dense Subset Sum may be the hardest considers cases where few subsets sum to any $X$. If you try their Lemma 3.1 with your unique sum property you get a $2^{0.406 n}$ algorithm. – Whosyourjay Mar 15 at 9:19