Assume there are non-negative numbers $\lambda_1\le \ldots\le \lambda_n\in[0,\infty)$. You are given the (ordered) list $s_1\le\ldots\le s_{2^n}\in[0,\infty)$ of all partial sums, i.e. every $s_i$ is of the form $s_i=\sum_{k\in K_i}\lambda_k$ for some unique but unknown $K_i\subseteq\{1,\ldots,n\}$.
Question: Can we determine the $\lambda_1,\ldots,\lambda_n$ from knowing the $s_1,\ldots,s_{2^n}$?
Some obvious facts are
- Since there is some $s_i$ corresponding to $K_i=\emptyset$, $s_1=\cdots=s_i=0$.
- $\lambda_1=s_2$, since no non-trivial partial sum can be smaller as the smallest possible summand.
- $s_{2^n}=\sum_{k=1}^n\lambda_k$, since no partial sum can be bigger.
- For $n=2$ the answer is yes, since $\lambda_1=s_2$ and $\lambda_2=s_4-s_2$.
Note: For my use case it would be sufficient to know if for any given $s_1\le\cdots\le s_{2^n}$ there is at most one possibility for $\lambda_1\le\cdots\le\lambda_n$.
Best Answer
By calculating how many $s_i$ are zero, you can determine how many $\lambda_i$ are zero. If there are any, they will be creating repeated entries $s_i$ throughout, but in a systematic manner where one can eliminate their effect; indeed, if there are $k$ zeroes, then there will be $k$ extra duplicates of every entry. For simplicity, suppose $\lambda_1 > 0$.
Now, indeed, $\lambda_1 = s_2$.
We proceed by induction. Suppose we have identified $\lambda_1,\ldots,\lambda_j$ and calculated the partial sums consisting of only $\lambda_1,\ldots,\lambda_j$, such as $\lambda_1+\lambda_3$. Then the smallest remaining partial sum must be $\lambda_{j+1}$. Proof: Otherwise the smallest remaining partial sum would have to be a sum with at least one unknown $\lambda_m$ that is (by definition) not yet in the list of known partial sums, which would imply that $\lambda_m$ is smaller than the smallest remaining partial sum; a contradiction.
Now that $\lambda_{j+1}$ is also known, consider the known list of partial sums to include all sums of $\lambda_1,\ldots,\lambda_{j+1}$.
Actually, separate treatment of steps 1 and 2 is not necessary; one only has to initialize the list of known partial sums with the empty sum $s_1=0$.
This method probably works even if you are missing entires from the list of partial sums, as long as all the missing entries are strictly greater than $\lambda_n$.