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

Question

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?

Answer 1

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.