# Partitioning a set of integers into 4 subsets with equal subset sums

Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other.

I am interested in an algorithmic solution.

-
Clearly it is not always possible: if the total sum is not a multiple of $4$ you can stop looking. Similarly if the sum of the smallest four and largest one is more than a quarter of the total sum, or if the sum of the largest four and smallest one is less than a quarter of the total sum you can stop. – Henry Feb 24 '12 at 15:59

This is at least as hard as the partition problem, which asks for only 2 subsets and is already NP-complete.

The known dynamic-programming solution to the partition problem can solve instances with integers less than 10000 without breaking much of a sweat. Unfortunately it doesn't behave nearly as nicely when generalized to create more than 2 subsets.

A brute-force search of all ways to divide your 20 inputs into 4 subsets should be doable in at most a few hours on ordinary desktop hardware.

But much better than that is possible: Follow a meet-in-the-middle strategy where you compute and store all the (about 50,000) unordered quadruples-of-sums that can be made from the first 10 inputs, and then explore whether any combination of the last 10 inputs happens to hit the complement of a known quadruple. That ought to complete in significantly less than a minute.

-
The number of ways to partition 20 objects into 4 subsets is about $10^{11}$, isn't it? – Gerry Myerson Feb 25 '12 at 4:20
@Gerry: Thereabouts, yes. With about $10^9$ clock cycles per second it would take some reasonably tight code to get down to an hour, but not a priori impossible. – Henning Makholm Feb 25 '12 at 5:21
@HenningMakholm Yes, your meet-in-the-middle strategy works fine. I improved the running time further by mapping the quadruples found in the first half to a boolean value. The map I used is a C++ map<multiset<int>, bool> which operates in logarithmic time as far as I know. Now it solves $41$ instances of the problem in less than $13$s. But the problem is actually from a programming contest and people solved this in a time limit of $3$s. So I think further improvement is possible. Here is my implementation. – f.nasim Feb 26 '12 at 15:09
@sven: Using a generic multiset is overkill when you know the multisets are always quadruples, and you can get away with only storing, say, the three smallest numbers, because the sum is always the same. Each of the three numbers will fit in 18 bits, so you can pack them all into a int64_t and use binary search in an int64_t[] instead of mucking around with generic containers. You don't need to keep the array sorted in the first phase; store them in the order you find them and then just sort the array once before moving to the second phase. All that should easily give you a factor of 4. – Henning Makholm Feb 26 '12 at 15:57