# 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:

"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."

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.

• This is a version of the NP-complete problem PARTITION. – Yuval Filmus Feb 12 at 10:33

## 1 Answer

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>0$$, $$OPT[0,x]=\bot$$.

If $$i>0$$: $$OPT[i,x] = \begin{cases} OPT[i-1,x] \vee OPT[i-1,x-a_i] & \mbox{if a_i \le x} \\ OPT[i-1,x] & \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\}$$.

• Could you elaborate on the dynamic programming approach? Should i check all possible partition's and compute the sum using dynamic progrmming? – sean python Feb 12 at 22:01
• If you check all possible partitions you're already using $\Omega(2^n)$ time. I'm editing my answer with the dynamic programming algorithm. Give me ~10 minutes. – Steven Feb 12 at 22:03
• What is the meaning of i in OPT[i,x]? – sean python Feb 13 at 13:19
• @seanpython, it means that we are only considering the first $i$ elements of $A$, i.e., the set $\{a_1, \dots, a_i\}$. – Steven Feb 13 at 14:54