Possible Original List

Question

Every List of n integers has its Sum List whose entries are all the possible sums of two different entries in the original List.

List => x1, x2, ... xn
Sum List => x1+x2, x1+x3, ... ,x2+x3, x2+x4 ..., xn-1+xn

List => 1, 2, 3, 4
Sum List => 3, 4, 5, 5, 6, 7

List of length n has Sum List of length n (n - 1) / 2

The goal is to find all possible original Lists given the Sum List and the length of the original List

Sum List => 1269, 1160, 1663
length of original List => 3
possible original List => 383, 777, 886

Sum List => 226, 223, 225, 224, 227, 229, 228, 226, 225, 227
length of original List => 5
possible original List => 111, 112, 113, 114, 115

How would you approach this?

---------------------------------------------

My approach is here:
https://code.sololearn.com/W0edzR3D8MkH/?ref=app

Answer 1

I used spaces to distiguish between elements of sum list and computation with those values. For example x1+x2 is the first element and I wrote it without spaces around the plus sign. So to compute x1 from the original list you need 3 elements from the sum list.

Minimal example (python code, so 0 based indices):
x = [1, 2, 4] # Original list, to be reconstructed
s = [3, 5, 6] # Sum list
x[0] = ( s[0] + s[1] - s[2] ) / 2 # = (3+5-6)/2 = 1
# For other values:
x[1], x[2] = s[0] - x[0], s[1] - x[0] # = 3-1, 5-1 = 2, 4

Answer 2

Benjamin Jürgens oh yes that's obvious. Thank you very much!

Answer 3

x1 = ( x1+x2 + x1+x3 - x2+x3 ) / 2

Then subtract x1 from the elements in sum list that contain x1 to get x2 to xn

Or you could repeat above scheme for x2 to xn

Answer 4

Benjamin Jürgens I don't get it. Could you please make it clearer? x1, x2 ... xn are unknown and figuring them out is the goal.