1
$\begingroup$

Question: I came a cross a problem where we have a set of numbers $W= \{x_1, \cdots, x_n\}$ where repetition of numbers is allowed. We would like to find out whether we can find out 3 disoint sets where the sum of numbers in each set is equal, e.g., $W=\{1,5,2,4,3,3\}$ can be split into 3 disjoint sets $(1,5), (2,4), (3,3)$ each with same sum that is $6$.

Base condition: So we can clearly see that the base condition for this problem to hold is $\frac W3$ is divisible otherwise it won't be solvable.

Approach 1: why we need dynamic programming? Because finding all permutations of a set would be $2^n$ and find their sums would take $2^n$, which is enough to tell this is a exponential time algorithm.

Approach 2: Let us formulate the problem with dynamic programming. First we start by building a table to fill up from subproblems (sets whose sum is to be found). The dimension of the table is $(\frac W3 + 1)(\frac W3 + 1)(n+1)$. For example, taking again $W=\{1,5,2,4,3,3\}$ can be split into 3 disjoint sets $(1,5), (2,4), (3,3)$, we can see that $W$ would be the sum we get from the disjoint groups, which is supposed to be the same for all 3. So the table $M$ would be of size $(3+1)\times(3+1)\times(7+1) = 4\times4\times8$. Then:

  • Define $M[x,y,k] = 1$ iiff there are two disjoint subsets $I,J \subset \{1, \cdots, k\}$ such that their summation is equal, that is $\Sigma_{i \in I} a_i = x$ and $\Sigma_{j \in J} a_j = y$.
  • Base case $k=0$, $M[0,0,0] = 1$ and $M[x,y,0] = 0$ for $x+y>0$.
  • Recursive step: $M[x,y,k] = M[x-a_k, y, k-1] \lor M[x, y-a_k, k-1] \lor M[x, y, k-1]$, for $k=1,\cdots, n$.
  • So, the solution will be at index $[\frac W3, \frac W3, n]$. Each index $M$ will select one of 3 ways to place a number $a_k$ in one of 3 disjoint sets $ M[x-a_k, y, k-1], M[x, y-a_k, k-1], M[x, y, k-1]$.

Problem 1: As I understand, we need to find 3 disjoint groups their sum is equal. So we build table whose rows and columns are simply from $0$ to last index $sum$ as $\frac W3$ will return one of the sums from the 3 groups as if all groups are equal, then their sum is $3 \times sum$, so dividing by 3 would give $sum$ which is the last index of the table $M$. So I am not sure why it's build in this way please given that we are looking for 3 groups disjoint having same sum. The recusrive step though is reasonable but still have problems undertsantind $x$ and $y$ which could be any number from $1$ to $sum$ in $M$.

enter image description here

Problem 2: as I understand from $M[x-a_k, y, k-1], M[x, y-a_k, k-1], M[x, y, k-1]$. Let us take 3rd group $M[x, y, k-1]$, it will loop over sum and then check upon removing an item from $x$, which we defined as sum from $x = Sum_{\{1, \cdots, k\}}$, and we store at $M[x, y, 0]$, for $k=0$. So how do you interpret the recursive operation as you see it based on description please?

$\endgroup$
5
  • 1
    $\begingroup$ Do you think it could be NP-hard? $\endgroup$
    – Pål GD
    Oct 21 '21 at 18:07
  • 1
    $\begingroup$ You can reduce PARTITION to your problem: given a PARTITION instance with sum $2S$, add another number equal to $S$. $\endgroup$ Oct 21 '21 at 18:14
  • $\begingroup$ @PålGD. Thanks for the question. Not sure Prof. $\endgroup$
    – Avv
    Oct 21 '21 at 18:39
  • $\begingroup$ @YuvalFilmus. Thanks Prof. I still not sure why we took the sum as the range of indices in out table matrix $M$ above. How would you interpret recursion formula above in your own words please? $\endgroup$
    – Avv
    Oct 21 '21 at 18:40
  • 1
    $\begingroup$ @Avra Could you please not write the word "please" in the middle of your sentences. It breaks the flow while reading the text. $\endgroup$ Oct 22 '21 at 9:57
1
$\begingroup$

I did not understand your question properly. But, I think you are asking for how the following identity holds: $M[x,y,k] = M[x-a_k, y, k-1] \lor M[x, y-a_k, k-1] \lor M[x, y, k-1]$

We want to check if there are two disjoint subsets $I,J \subset \{1, \cdots, k\}$ such that $\Sigma_{i \in I} a_i = x$ and $\Sigma_{j \in J} a_j = y$. There are three possibilities for $M[x,y,k]$ to be true:

  1. The element $a_{k}$ belongs to $I$.

  2. The element $a_{k}$ belongs to $J$.

  3. The element $a_{k}$ neither belongs to $I$ or $J$. It means it belongs to the third set.

For the first possibility, observe that $M[x,y,k] = 1$ only if $M[x-a_{k}][y][k-1] = 1$.

For the second possibility, observe that $M[x,y,k] = 1$ only if $M[x][y-a_{k}][k-1] = 1$.

For the third possibility, observe that $M[x,y,k] = 1$ only if $M[x][y][k-1] = 1$.

It implies that $M[x,y,k] = 1$ if and only if $M[x-a_k, y, k-1] \lor M[x, y-a_k, k-1] \lor M[x, y, k-1] = 1$.

Suppose you have computed all the entries of the form $M[.][.][k-1]$. Then, using the above identity you can compute all the entries of the form $M[.][.][k]$, and so on.

For this, you require to initially fill up the table for $k = 0$. All the entries of the form $M[.][.][0]$ are $0$ except $M[0][0][0]$ since without using any element from the array you can not create a non-zero sum $x$ or $y$.

Let me know, if it answers your question.

$\endgroup$
2
  • $\begingroup$ So how what will $M[x][y][k]$ stands for each iteration please? What the rows and columns of our table $M$ stand for? $\endgroup$
    – Avv
    Oct 22 '21 at 12:15
  • 1
    $\begingroup$ @Avra It is given in your answer that: "$M[x,y,k] = 1$ iiff there are two disjoint subsets $I,J \subset \{1, \cdots, k\}$ such that their summation is equal, that is $\Sigma_{i \in I} a_i = x$ and $\Sigma_{j \in J} a_j = y$." I do not understand what else to explain here. :) $\endgroup$ Oct 22 '21 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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