# Partition of a set of integers into subsets with prescribed sums

I saw this problem:

A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,...,S_k$ such that $\sum_{x\in S_i} x = m_i$ for each $1\leq i \leq k$.

in the paper "PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH PRESCRIBED SUMS", by Fu-Long Chen, Hung-Lin Fu, Yiju Wang and Jianqin Zhou

http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028

They have solved the problem under certain constraints. But I can't find anything about its complexity in general. Does anyone know a reference about the complexity of this problem? It reminds me of the bin-packing problem, or in some sense, it is similar to the subset sum problem. So, I guess it must be NP-complete in general?

More precisely, I like to prove the NP-completeness for the fixed value of $k$, for example, when $k = 3, 4, \ldots$? In this case, it is very similar to bin-packing or knapsack problem, but as we want the equality it is different. Maybe there are variations of these problems that match my question?

• I would be very surprised if this problem was NP-complete. Feb 28 '15 at 19:33
• @user24175 Is it known to be polynomial time solvable if every $S_i$ has cardinality 2? Mar 1 '15 at 11:47
• @mohammad If every $S_i$ has cardinality $2$, then we can reduce the problem to bipartite matching as follows. Consider $n$ vertices, labelled $1$ to $n$. There is an edge between vertex $i$ and vertex $j$ if there is a value $t$ such that $i + j = m_t$. Mar 3 '15 at 10:30
• @S.Pek That is incorrect. We need to find a restricted perfect matching with certain some ($\sum m_i$ ) If we want any perfect matching then the problem is polynomial time solvable. So, the problem probably is $NP$-complete even if every $S_i$ has cardinality 2. Mar 3 '15 at 12:13
• @mohammad It is not $\sum m_i$, but rather $\sum_{x \in S_i} x = m_i$. Mar 3 '15 at 12:46

For any fixed $k$, isn't it in P, by dynamic programming?

For each $i\in\{0,\ldots,n\}$ and $t_1, t_2, ..., t_k$ such that each $t_i \in \{0,\ldots,m_i\}$, define $S(i, t_1, t_2, \ldots, t_k)$ to be true iff $(t_1, t_2, .., t_k)$ is $i$-realizable. Then there are $O(n^{2k+1})$ such subproblems (assuming WLOG that $\max_i m_i\le n^2$), and you have a recurrence like

$S(i, t_1, t_2, \ldots, t_k)$

$~ = S(i-1, t_1 - i, t_2, \ldots, t_k)$

$~\vee~ S(i-1, t_1, t_2 - i, t_3, \ldots, t_k)$

$~\vee~ \cdots$

$~\vee~ S(i-1, t_1, t_2 , t_3, \ldots, t_{k-1}, t_k- i)?$

This problem is known to be NP-complete in the strong sense. See for instance
https://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle/713

• @ Gamow: Thank you so much. But I actually had the proof that they suggested, by reduction from the partition problem instead of the 3-partition problem, quite a similar argument. I actually am looking for a proof that can be applied to any fixed value of $k$ (the number of sticks), for example, when $k=3$? Following the proof in that page, to achieve the NP-completeness for $k=3$, we have to set up, $a_1=1,\ldots,a_{3n}=N$, and $n=3$, which does not satisfy the conditions for the 3-partition problem, and indeed it is a very special instance of the problem! Mar 9 '15 at 7:47