# Is the following special case of multiway number partitioning NP-hard?

The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $$k$$ is also a part of an input in the following problem, while $$k$$ is a fixed number in wikipedia definition).

Given $$k, n \in \mathbb{N}$$ and $$n$$ numbers $$a_1, \ldots, a_n \in \mathbb{Z}$$, decide if there exists a partition of the numbers into $$k$$ parts so that the sum of numbers in each part equals $$\frac{\sum a_i}{k}$$.

As this problem includes the partition problem as its special case (i.e. $$k=2$$), multiway number partitioning is NP-hard.

I would like to know whether the hardness still holds for the following special case of multiway number partitioning (The only difference is that we assume each number is $$0$$ or $$1$$).

Given $$k, n \in \mathbb{N}$$ and $$n$$ numbers $$a_1, \ldots, a_n \in \{0,1\}$$, decide if there exists a partition of the numbers into $$k$$ parts so that the sum of numbers in each part equals $$\frac{\sum a_i}{k}$$.

In this special case, when $$k$$ or $$n-k$$ is a fixed constant, it is easy to see that the problem is polynomial-time solvable. This is because if $$k$$ is a constant, you can use dynamic programming and if $$n-k$$ is a constant, the number of possible partitions is at most the polynomial of $$n$$, hence you can check the condition directly.

As there seems to be no efficient algorithm for middle size $$k$$, I conjecture that multiway number partitioning for this special case is still NP-hard.

I would like to know if anybody knows about this.

• Since all input numbers are $0$ or $1$, such a partition exists if and only if $(\sum a_i)/k$ is an integer. This is trivial to check in polynomial time. Jan 13 at 17:02
• Nice first question! Welcome to our community! Jan 14 at 0:10
• To extend @Gamow's observation, the straightforward dynamic program for a problem with element universe $U = \{0,1,...,u\}$ has running time $O(nku^{k-1})$. When $u=1$, the only truly expensive part of the algorithm drops out. Jan 14 at 4:21
• Thank you so much for the solultion. I should have come with that. Jan 14 at 6:59