Separating set of integers
I have a problem with a solution for an algorithmic problem as described below.
We have a collection (like an array) of integers. Our task is to divide them into groups (they should not have the same number of elements), that the sum is equal to each other. In the case when the primary set cannot be divided, we must answer "cannot be divided".
For example: Install A
set [-7 3 3 1 2 5 14]
. Answer: [-7 14], [3 3 1], [2 5]
.
It seems easy to tell when it would be impossible for sure. If the sum of the primary set is not divisible by 3: sum(A) % 3 != 0
.
Do you have any idea how to solve this problem?
source to share
This is a problem with 3 partitions variant partition problem , the difference is that the classic partition problem splits the set into two sets (not three), the sums of which are equal to each other. This problem is NP-complete, so you almost certainly won't find a polynomial time solution for it; the 2-partition problem has a pseudo-polynomial workaround, but the 3-partition problem fails.
See this answer for a description of how to adapt a two-section algorithm to a three-section algorithm. See also this document for a parallel solution.
source to share