**Edit:** This question has been reasked [on TCS](https://cstheory.stackexchange.com/questions/42502/subset-sum-problem-with-at-most-one-solution-for-any-target).

---

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.