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.
