Dividing set of integers

2.1k views Asked by At

I've got a problem with a solution for algorithmic problem as described below.

We have a set (e.g. array) of integers. Our task is to divide them into the groups (they don't have to have same amount of elements) that sum is equal to each other. I case that primal set cannot be divide we have to give answer "impossible to divide".

For example: Set A is given [-7 3 3 1 2 5 14]. The answer is [-7 14], [3 3 1], [2 5].

It seems that it's easy to say when for sure it would be impossible. When sum of primal set isn't divisible by 3: sum(A) % 3 != 0.

Do you have any idea how to solve that problem?

1

There are 1 answers

1
Zim-Zam O'Pootertoot On BEST ANSWER

This is the 3-partition problem variant of the partition problem, the difference being that the classic partition problem splits the set into two sets (not three) whose sums are equal to each other. This problem is NP-complete, so you're almost certainly not going to find a polynomial time solution for it; the 2-partition problem has a pseudopolynomial time solution, but the 3-partition problem does not.

See this answer for an outline of how to adapt the 2-partition algorithm to a 3-partition algorithm. See also this paper for a parallel solution.