Partitioning list into two parts of almost equal sum I was given this problem in class, and I have no idea how to solve it. The problem is:

&quot;Given a list of positive integers, divide the numbers into 2 groups such that the difference between the sum of each group is minimal, print that difference. The algorithm must be efficient.&quot;

I guess by efficient they mean do not just brute force every option, any ideas?
I tried summing all the numbers and dividing by 2, then the problem is equivalent to finding a group that is the closest to that number, also now you can go over all  the options but once you get to a point where you can only add numbers but your above that number you  can stop.
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\}$.