N subsets with a given sum?

Question

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.

Answer 1

Let us define a predicate
$$T(i,k_1,...,k_n)\in\{True, False\}$$ Where $T(i,k_1,...,k_n)$ means "using the $i$ first values of $S$, we can find $n$ disjoint subsets with sums $k_1, ... k_n$".
The answer you are looking for is $T(|S|,K,..,K)$ where $K$ appears $n$ times.
We have the following recurrence formula : $$T(i,k_1,...,k_n) = \left\{ \begin{matrix} T(i-1,k_1,...,k_n) & \text{// we don't use value $x_i$} \\ \vee T(i-1,k_1-x_i,...,k_n) \text{ if $x_i \geq k_1$} &\text{// we put value $x_i$ in set 1}\\ \vdots \\ \vee T(i-1,k_1,...,k_n-x_i) \text{ if $x_i \geq k_n$} &\text{// we put value $x_i$ in set n}\\ \end{matrix}\right.$$ This formula is a big boolean "or", I don't know how I could make it look better.
We also the following initialisation : $\forall i, T(i,0,...,0) = True$.
You can see it as a big $n+1$-dimensional array, where the first dimension has length $|S|$, and the others have length $K$, which gives $O(K^n|S|)$ values. In that array, all the values can be computed from the other values in time $O(n)$ (the big "or" is over $n+1$ values).
Therefore, the worst case complexity is $O(nK^n|S|)$.

About implementation, it might be easier to do with recursively with memorization. However, you're gonna blow up the stack really fast, so you might want to think of something iterative.

To get the actual values in each set, run a backtracking algorithm once you have that truth array.

Answer 2

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.

Answer 3

Assuming the subsets are disjoint, we first assume we have a blackbox algorithm SUBSET, which given a set $S = [x_1, x_2, x_3,...x_n]$ and an integer $k$, will return a set $T$ such that $T$ is a subset of $S$, i.e $T \subset S$. Given a number $n$, which will be the number of subsets we want to generate, the algorithm is as follows.

ret = {}
(While n > 0)
     T = SUBSET(S,k)
     ret.add(T)
     S = S / T
     n -= 1
return ret

In this snippet, I assume $S$ is the initial subset, $k$ is the desired sum, and $n$ is the number of subsets we want. Each time we calculate a subset, we calculate the set difference of $S$ and $T$ and set the resulting set equal to $S$, essentially removing the element of $T$ from $S$. Now, for the implementation of SUBSET, if you go with the dynamic programming approach, you can achieve a runtime of $O(xnk)$, where $n = |S|$. More info on the dynamic solution can be found here. https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm. If you really want to optimize the runtime of SUBSET, the fastest algorithm I could find is outlined in this paper https://arxiv.org/abs/1507.02318, although it may not be practical to implement. If you're looking for a polynomial time algorithm, then I'm afraid you're out of luck since this problem reduces to SUBSET, which is an NP-Complete problem.