# Partitioning a set to the maximum number of subsets summing to zero

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.

• What exactly is your question? Looking for algorithms? Hardness proofs? References? – Tom van der Zanden Feb 6 '16 at 17:31
• 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. – 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$.