<p>Given a multiset <span class="math-container">$S$</span> of positive integers and a fixed positive integer <span class="math-container">$k$</span>, can <span class="math-container">$S$</span> be partitioned into <span class="math-container">$k$</span> parts with equal sum?</p>
<p>For <span class="math-container">$k = 2$</span>, this is the well-known Partition problem. For general <span class="math-container">$k$</span>, this is described on <a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning" rel="nofollow noreferrer">Wikipedia</a> as the &quot;multiway number partitioning&quot; problem, and it's claimed there that this problem is NP-hard for every fixed <span class="math-container">$k$</span>. However, the reference provided there is not satisfactory because it is about a different problem. I also cannot find this problem in Garey and Johnson's &quot;Computers and Intractability: A Guide to the Theory of NP-Completeness&quot;.</p>
<p>Is there a good reference for the NP-hardness of this problem?</p>

CC BY-SA 4.0
2024-01-06T17:35:00.573Z
This is not a research level question. Try posting to https://cs.stackexchange.com.
domotorp
CC BY-SA 4.0
2024-01-06T23:47:26.997Z
Cross-posted: https://cstheory.stackexchange.com/q/53745/5038, https://cs.stackexchange.com/q/164884/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  If you post on the wrong site, you can delete the copy on the wrong site before posting on a new site.
D.W.
<reference-request><partition-problem>
NP-hardness of partitioning into k sets
user71821
# NP-hardness of partitioning into k sets

(Asked by: username_0 on 2024-01-06)

Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum?

For $k = 2$, this is the well-known Partition problem. For general $k$, this is described on [Wikipedia](https://en.wikipedia.org/wiki/Multiway_number_partitioning) as the "multiway number partitioning" problem, and it's claimed there that this problem is NP-hard for every fixed $k$. However, the reference provided there is not satisfactory because it is about a different problem. I also cannot find this problem in Garey and Johnson's "Computers and Intractability: A Guide to the Theory of NP-Completeness".

Is there a good reference for the NP-hardness of this problem?

**Tags:** reference-request, partition-problem
> **Comments:**
> **username_1**: This is not a research level question. Try posting to https://cs.stackexchange.com.  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/53745/5038, https://cs.stackexchange.com/q/164884/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  If you post on the wrong site, you can delete the copy on the wrong site before posting on a new site.  

---

## 0 answers

