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.
[Math] Partitioning a set of integers into 4 subsets with equal subset sums
algorithmscombinatoricscomputer sciencediscrete mathematics
Best Answer
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.