Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
