Can we determine summands from their partial sums?

Question

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

1. Since there is some $s_i$ corresponding to $K_i=\emptyset$, $s_1=\cdots=s_i=0$.
2. $\lambda_1=s_2$, since no non-trivial partial sum can be smaller as the smallest possible summand.
3. $s_{2^n}=\sum_{k=1}^n\lambda_k$, since no partial sum can be bigger.
4. 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$.

Answer 1

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

2. Now, indeed, $\lambda_1 = s_2$.

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

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

Answer 2

Here is a streamlined version of Tommi Brander's solution: $\newcommand{\IN}{\mathbb{N}}$

Lemma: Let $0\le\lambda_1\le\cdots\le\lambda_n$ and $\mathcal{P}\doteq\left\{\lambda_K\doteq\sum_{k\in K}\lambda_k\left|K\subseteq\mathbb{N}_n\right.\right\}$ the set of their partial sums, where $\IN_n\doteq\{1,2,\ldots,n\}$. For $0\le l\le n$ consider the function $m_l:\mathcal{P}\to\IN_0$ with $m_l(\lambda)=\#\{K\subseteq\IN_l\mid\lambda_K=\lambda\}$. Then for all $1\le l\le n$, \begin{equation} \lambda_l=\min\left\{\lambda\in\mathcal{P}\mid m_{l-1}(\lambda)<m_n(\lambda)\right\}. \end{equation} In particular, noting that $m_0(\lambda)=\mathbf{1}(\lambda=0)$, the $\lambda_1,\ldots,\lambda_n$ can be recovered iteratively only from $\mathcal{P}$ and $m_n$.

Proof: Let $\mathcal{P}_l\doteq\left\{\lambda\in\mathcal{P}\mid m_{l-1}(\lambda)<m_n(\lambda)\right\}$. By construction, $\lambda_l\in\mathcal{P}_l$ and therefore $\lambda_*=\min\mathcal{P}_l$ exists and satisfies $\lambda_*\le\lambda_l$. Since $m_{l-1}(\lambda_*)<m_n(\lambda_*)$, there is some $K\subseteq\IN_n$ with $K\not\subseteq\IN_{l-1}$ such that $\lambda_*=\lambda_K$. In particular there is $r\in K$ with $r\ge l$ and, hence, $\lambda_r\in\mathcal{P}_l$. By positivity of the $\lambda_i$ we find that $\lambda_r\le\lambda_K=\lambda_*$ and therefore $\lambda_*=\lambda_r$ by minimality of $\lambda_*$. Since $r\ge l$ we conclude $\lambda_l\le \lambda_r=\lambda_*\le\lambda_l$, thus $\lambda_*=\lambda_l$.