Solve the Turnpike Problem solved by 219

If A = (a₁ = 0, a₂, ... , a_n) is a set of n points on a line segment in increasing order (a₁ < a₂ < · · · < a_n), then $\Delta$A denotes the collection of all pairwise differences between points in A. For example, if A = (0, 2, 4, 7), then

The following problem asks us to reconstruct A from $\Delta$A.

Turnpike Problem

Given all pairwise distances between points on a line segment, reconstruct the positions of those points.

Given: A collection of integers L.

Return: A set A such that ∆A = L.

Sample Dataset

-10 -8 -7 -6 -5 -4 -3 -3 -2 -2 0 0 0 0 0 2 2 3 3 4 5 6 7 8 10

Sample Output

0 2 4 7 10

Extra Dataset

Click for an extra dataset