Original Proposer: noko0

When \(N=1\), the answer is \(A_1^2\).
Assume \(2 \leq N\).
The final \(x\) can be represented as \(x=\sum_{i=1}^{N}{c_iA_i}\), where \(c_i\) is \(1\) or \(-1\).
We have \(x^2=\sum_{i=1}^{N}{{A_i}^2}+2\sum_{1 \leq i \lt j \leq N}{c_ic_jA_iA_j}\), but \(\sum_{i=1}^{N}{{A_i}^2}\) is independent of \(c_i\).
The expected value of \(\sum_{1 \leq i \lt j \leq N}c_ic_j\) is dependent only on \(N\), so let us write this \(C_N\).
The probability of obtaining \((c_1,c_2,\dots,c_N)\) is equal as long as it is equal as a multiset, and \((c_1, c_2,\dots,c_N)\) is independent of \((A_1, A_2,\dots,A_N)\), so we have
\(E[\sum_{1 \leq i \lt j \leq N}{c_ic_jA_iA_j}]=C_N\frac{\sum_{1 \leq i \lt j \leq N}{A_iA_j} }{\frac{N(N-1)}{2}}\).
Since \(\sum_{1 \leq i \lt j \leq N}{A_iA_j}=\frac{(\sum_{i=1}^{N}{A_i})^2-\sum_{i=1}^{N}{A_i^2}}{2}\),
all that left is to compute \(C_N\).
Recall the assumption \(2 \leq N\). Without loss of generality, we may assume that we remove \(A_1\) and \(A_2\) and push \((A_1-A_2)\) in the first step.
In this case, \(c_1\) and \(c_2\) will always have different signs regardless of the remaining operations, so
\(c_1c_2=-1\),
\(c_1c_i+c_2c_i=0 \; (3 \leq i \leq N)\).
For \(3 \leq i \lt j \leq N\), the expected value of \(c_ic_j\) is equal to the expected value of \(c_ic_j\) when there are \((N-1)\) elements, so \(\frac{C_{N-1}}{\frac{(N-1)(N-2)}{2}}\).
Hence, \(C_N=-1+\frac{C_{N-1}}{\frac{(N-1)(N-2)}{2}}\frac{(N-2)(N-3)}{2}=-1+\frac{N-3}{N-1}C_{N-1}\).
With \(C_1=0\), we can compute \(C_2,C_3,\dots,C_N\) incrementally by the recurrence relation.
The total complexity is \(O(N)\).