Q:

Restoring permutation from differences of adjacent elements

Suppose a permutation $\pi \in S_n$ is encoded by a list of integers $P=(p_1, p_2, ... p_{n-1})$, where $p_i = \pi(i+1) - \pi(i)$, i.e. $P$ is the list of differences of adjacent elements. Now, given $P$, is it possible to restore the original permutation $\pi$ (or to tell that there is no solution)?

A:

Create the list
$$(q_1,\ldots,q_{n-1})$$
where
$$q_m=\sum_{i=1}^m p_i$$
Then
$$q_m=\pi(m+1)-\pi(1)$$
$\pi(1)$ is equal to the number of $q$ that are negative, plus $1$. We reconstruct the permutation by putting this element first and adding it to all $q$. There is a solution if and only if this is a permutation. 

