N subsets with a given sum? How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?

¹⁾ Not as in $P$, I just want something smarter than $O(n^{|S|})$.



Ex. Let’s say we want $n=3$ subsets with the sum of $K=3$ chosen from $S=[1,1,1,2,2,2]$.

The correct solution is $[1,2], [1,2], [1,2]$.



Ex. Let’s say we want $n=2$ subsets with the sum of $K=5$ chosen from $S=[5,4,3,2,2,2,2,1]$.

One correct solution is $[5], [1,4]$.

Another one would be $[2,2,1], [2,3]$.



Etc. Just a correct solution, regardless of which one.
This problem is strongly NP-hard because it generalizes the 3-Partition problem. That means that it has no efficient (polynomial-time) algorithm, unless P=NP.