# Find if it's possible to partition a set into 3 disjoint sets each with same sum

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$$.

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?

• Do you think it could be NP-hard? Oct 21 '21 at 18:07
• You can reduce PARTITION to your problem: given a PARTITION instance with sum $2S$, add another number equal to $S$. Oct 21 '21 at 18:14
• @PålGD. Thanks for the question. Not sure Prof.
– Avv
Oct 21 '21 at 18:39
• @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?
– Avv
Oct 21 '21 at 18:40
• @Avra Could you please not write the word "please" in the middle of your sentences. It breaks the flow while reading the text. Oct 22 '21 at 9:57

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$$.

• So how what will $M[x][y][k]$ stands for each iteration please? What the rows and columns of our table $M$ stand for?
• @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. :) Oct 22 '21 at 16:42