3

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?

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
Pączek W Maśle
  • 33
  • 4
  • Do you have to partition the given array into 3 pieces? Also, what solution complexity are you looking for? – Pradhan Dec 14 '14 at 23:17
  • A trivial solution is to simply return the original set! – Rafe Dec 14 '14 at 23:39
  • The solution is impossible even if we cannot divide into 3 such sets. For example, {1000, 1001, 1002, 3} has a sum divisible by 3 but the division into subsets with equal sums is impossible. – user1952500 Dec 14 '14 at 23:57
  • @user1952500: that's not what Pączek said. If the sum is *not* evenly divisible by the number of sets, then you are *sure* it's not possible. The question is, what if it is? – Jongware Dec 15 '14 at 00:06
  • @Jongware The first statement did not say that. The second was what you said. – user1952500 Dec 15 '14 at 00:10
  • Surely the problem is to find *all* such groupings, otherwise as @Rafe says, the identity function would suffice. – Chris Martin Dec 15 '14 at 00:12
  • @Rafe Haha, that would be an answer but I forgot to mention that we have to partition array to 3 pieces. And we don't need to find all solutions. It's necessary to find at least one or to say that it's impossible to partition. – Pączek W Maśle Dec 15 '14 at 09:11

1 Answers1

3

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.

Community
  • 1
  • 1
Zim-Zam O'Pootertoot
  • 17,888
  • 4
  • 41
  • 69
  • Thank you @Zim-Zam O'Pootertoot! I hadn't knew the partition problem so I didn't know about what should I ask;) Both linked, answer and paper, I've found very useful and interesting. – Pączek W Maśle Dec 15 '14 at 10:05