I am stuck at the complexity of the following problem: Given a multiset $S = \{x_1,..., x_n\}$ of $n$ integers and a natural number $k$. Can $S$ be partitioned into multisets $S_1,... S_j$ such that for all $S_i \subseteq S$ there is $\sum_{ s \in S_i} s = k?$

I have found out that this may be somehow related to the EqualSubetSum Problem or the partition problem. But is this problem really $NP$-complete or exists a polynomial algorithm depending on $k$ and $n$ to decide this problem?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top