2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – GBat Jan 12 at 13:48
  • $\begingroup$ Also, should the sets be disjoint ? $\endgroup$ – GBat Jan 12 at 13:54
  • $\begingroup$ @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. $\endgroup$ – Michal Rus Jan 12 at 20:59
  • $\begingroup$ 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. $\endgroup$ – GBat Jan 12 at 21:17
  • $\begingroup$ 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). =( $\endgroup$ – Michal Rus Jan 12 at 23:26
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – Michal Rus Jan 14 at 15:30
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michal Rus Jan 12 at 13:00
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 ]$. $\endgroup$ – Vincenzo Jan 11 at 8:59
  • 1
    $\begingroup$ In fact the "Polynomial time approximate algorithm" just tell you if you can build a new set without gauranteeing that it is the best choice. If you greedily stack these sets you may be blocked as showed by Vicenzo. If you search next set following decreasing values, I believe this issue cannot happen. But this is not directly compatible with this particular algorithm. $\endgroup$ – Vince Jan 11 at 9:45
  • $\begingroup$ What if SUBSET was defined so that it uses up larger numbers first? Could we still get a block? I can’t find a counterexample. $\endgroup$ – Michal Rus Jan 11 at 15:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.