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 $$, [1,4]$$.

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

Etc. Just a correct solution, regardless of which one.

• I think one can find a $O(K^{n}|S|)$ dynamic programming solution, where $K$ is the sum of each subset. Would that be better ? – GBat Jan 12 at 13:48
• Also, should the sets be disjoint ? – GBat Jan 12 at 13:54
• @GBat $O(K^n |S|)$ would be amazing. ♥ But how to do this? I thought about it for a while, but, to me, this problem seems not to have an optimal structure for DP… Yes, the subsets need to be disjoint. – Michal Rus Jan 12 at 20:59
• Do you know the dynamic programming for the 2 partition problem ? I think we can find something like this. I'll think about it and post an answer tomorrow if I find it. – GBat Jan 12 at 21:17
• Yes, 2-partition is just a Subset Sum problem with said sum equal to half the sum of all input elements. But if you find one such subset, the other one is given immediately — so this really is Iterative Subset Sum (with just a single iteration). Here, we need to find $n$ such subsets, and if we used Iterative Subset Sum, it’ll get blocked eventually… (as shown by @Vincenzo below, in comments). =( – Michal Rus Jan 12 at 23:26

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.

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.

• Yes, yes, it’s obviously not in P, sorry for confusion, I shouldn’t have used the word “efficient”. What I meant was that I just wanted something smarter than $O(n^{|S|})$ if $n$ is the number of desired subsets and $S$ the input set. – Michal Rus Jan 12 at 13:00

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)
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.
• This approach is not correct in general. Suppose $k=7$, $x=3$ and $S=[ 1,1,1,1,1,1,1, 2, 3,3, 6]$. Let's say in the first iteration the algorithm chooses $T=[1,1,1,1,1,1,1]$. Then $S\setminus T = [ 2, 3, 3, 6 ]$, which cannot be further divided into two sets of value $7$. However, the initial instance has a solution, namely, $[ 1, 6 ]$, $[ 1, 1, 1, 1, 3 ]$, $[ 1, 1, 2, 3 ]$. – Vincenzo Jan 11 at 8:59