Partitioning list into two parts of almost equal sum
As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$).
You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the sum of the input integers, using dynamic programming, or in time $O(n \cdot 2^{n/2})$ using the split-and-list technique. Pick the best of the two algorithms depending on the value of $S$.
The dynamic programming algorithm is as follows.
Let $A = \{a_1, \dots, a_n\}$ be the input (multi-)set of numbers, and let $S=\sum_{a \in A} a$.
Consider a partition of $A$ into two sets $B$ and $C$, and assume w.l.o.g. that $\sum_{b \in B} b  \le \sum_{c \in C} c$ (since otherwise you can swap $B$ and $C$).
The cost (to minimize) of this partition is:
$$
\sum_{c \in C} c - \sum_{b \in B} b =
\left(S- \sum_{b \in B} b\right) - \sum_{b \in B} b  
= S - 2 \sum_{b \in B} b.
$$
Showing that the problem is equivalent to finding a subset $B$ of $A$ whose sum of elements is at most $\lfloor S/2 \rfloor$ and, subject to this constraint, it is maximized.
For $i=0, \dots, n$, and $x=1,\dots,\lfloor S/2 \rfloor$, let $OPT[i,x]$ be true if and only if there exists a subset $B$ of $\{a_1, \dots, a_i\}$ with $\sum_{b \in B} b = x$.
Then $OPT[0,0]=\top$ and, for $x&gt;0$, $OPT[0,x]=\bot$.
If $i&gt;0$:
$$
OPT[i,x] = \begin{cases}
OPT[i-1,x] \vee OPT[i-1,x-a_i] &amp; \mbox{if $a_i \le x$} \\
OPT[i-1,x] &amp; \mbox{otherwise}
\end{cases}.
$$
There are $O(nS)$ values $OPT[i,x]$ and each of them can be computed in constant time (in increasing order of $i$).
The maximum value of $\sum_{b \in B} b$ is $\max \left\{ x \in \{0, \dots, \lfloor S/2 \rfloor \} \mid OPT[n, x] = \top \right\}$.