Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero?

I have searched around a lot, but none of the partition or packing problem variants seem to address this particular case.

  • $\begingroup$ What exactly is your question? Looking for algorithms? Hardness proofs? References? $\endgroup$ – Tom van der Zanden Feb 6 '16 at 17:31
  • $\begingroup$ I'm looking for an algorithm, yes. I have an implementation of the dynamic programming solution, which I can use to find some subsets, but I don't know how to continue from there on, or if i'm on the right track at all. $\endgroup$ – mgunyho Feb 6 '16 at 17:47

3-Partition reduces to this problem, so it's strongly $NP$-hard. Moreover, 4-Partition also reduces to it (and the blowup is linear), so assuming the exponential time hypothesis there's no $2^{o(n)}$ algorithm.

Using dynamic programming there's a $O^*(4^n)$ algorithm, it would be interesting if you could do $2^n$ or even $1.99^n$.

  • 1
    $\begingroup$ Can you specify the algorithm? $\endgroup$ – mgunyho Feb 6 '16 at 17:48
  • $\begingroup$ @mgunyho Here is the actual reduction to the 3-partition problem I think :) $\endgroup$ – iago-lito Aug 26 '18 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.