Partition square root from 1 to 50 into two sets of equal sum The numbers  $\{\sqrt{1},\sqrt{2},\sqrt{3},\sqrt{4}, \dots \sqrt{50}\}$ are to be partitioned into two sets whose sum is most nearly equal. Find the most nearly partition you can, using the least amount of computer processor time but no more than $10$ seconds of computer processor time.
I have to make a computer program but I can't understand which algorithm to use.
 A: I guess it is impossible to find polynomial of $n$ solution for set $\{\,\sqrt1, \sqrt2, \ldots, \sqrt n\,\}$ of numbers unless $\mathrm P = \mathrm{NP}$. However I wouldn't prove this conjecture. Because I can suggest an approach that takes $\mathrm O(n\cdot 2^{n / 2})$ time for even more general case, i. e., for arbitrary (multi-)set $\{\,a_1, a_2, \ldots, a_n\,\}$ of numbers. For $n = 50$ it should take $1$ second or less on any modern computer.
If we want to get two part with the most equal sums then it is the same when we want to minimize an absolute value of sum $S(\overline{\alpha})(-1)^{\alpha_1}a_1 + (-1)^{\alpha_2}a_2 + \cdots + (-1)^{\alpha_n}a_n$ subject to $\alpha_i \in \{\,0, 1\,\}$. We will use it further.
So at first we separate all numbers into two almost equal parts. I. e., let $k = \left\lfloor \frac{n}{2}\right\rfloor$, then $A = \{\,a_1, a_2, \ldots, a_k\,\}$ and $B = \{\,a_{k + 1}, \ldots, a_{n - 1}, a_n\,\}$. Now we can compute collection $S_A$ of all possible sums $(-1)^{\alpha_1}a_1 + (-1)^{\alpha_2}a_2 + \cdots + (-1)^{\alpha_k}a_k$ for $\alpha_i \in \{\,0, 1\,\}$ in $\mathrm O(2^k)$ time. (However you can do it in the most trivial way using $\mathrm O(k\cdot 2^k)$ time that is acceptable.) In other words we consider separation of $A$ into two parts and subtract sum of the second part from sum of the first part for all possible separations. The same we can do to compute $S_B$ that is collection of all possible similar sums for $B$.
After that we sort one of them, say $S_A$, using $\mathrm O(|S_A| \log |S_A|) = \mathrm O(2^k \cdot k)$ time. Then for each element $s$ of $S_B$ we can find an element $t(s)$ of $S_A$ that is the closest to $s$ among all elements of $S_A$. Just use binary search for that purpose and use $\mathrm O(\log |S_A|) = O(k)$ time for each of $O(2^k)$ elements of $B$. So we have $\mathrm O(\log k \cdot 2^k) = \mathrm O(n \cdot 2^{n / 2})$ time in total. Getting for $s \in S_B$ the closest to $s$ element $t(s) \in S_A$ we minimize the absolute value of $s + t(s)$ and therefore taking minimum over all $s \in S_B$ we get we minimum of $S(\overline{\alpha})$ as desired.
