Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

Question

Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

Answer 1

Yes, there is a pseudo-polynomial algorithm for this problem.

---

Here is a wrong algorithm. Can you spot the biggest error?

Let $K=\sum_{i=1}^n{a_i}$. If $K$ is not divisible by 3, return none.

Run the pseudo-polynomial algorithm with $\lfloor K/2\rfloor$ replaced by $K/3$ everywhere. Adapting the algorithm so that it tracks the set of numbers whose sum is a given number. If that run of that algorithm return false, return none. If yes, remove the set of numbers from $a_1, a_2, \cdots, a_n$, we reduce the problem to find a subset of the remaining numbers whose sum is $K/3$, or half of the sum of remaining numbers, which is, of course, the partition problem again and which can be solved in pseudo-polynomial time.

---

Let us see how to construct a correct algorithm.

In the pseudo-polynomial algorithm for partition into two disjoint subsets, the goal is to compute function $p$ such that $p(i, j)$ is True if a subset of $\{x_1, \cdots, x_j \}$ sums to $i$ and False otherwise.

Now for partition into three disjoint subsets we have two variable parts, the first subset and the second subset (the third subset is the remaining integers), our goal is to compute function $q$ such that $q(h,i,j)$ is True if there are two disjoint subsets of $\{x_1, \cdots, x_j \}$ such that one of them has sum $h$ and the other has sum $i$, where $0\le h\le K/3, 0\le i\le K/3$. We have the following recurrence relation, ignoring a few corner cases because of the out-of-bound situations that are easy to figure out.

$q(h, i, j)$ is True if either of the following is true.

• $q(h, i, j − 1)$
• $q(h, i − x_j, j − 1)$
• $q(h-x_j, i, j − 1)$

$q(h, i, j)$ is False otherwise.

I will leave the rest for readers to figure out.

---

Exercise 1. Write the correct algorithm roughly or fully in pseudocode or in your favorite programming language. Adapt it so that it will track the subsets in order to return the wanted three disjoint subsets.

Exercise 2. Show the time-complexity of the correct algorithm is $O(nK^2)$.

Exercise 3. Generalize to PARTITION-INTO-M-SETS for any given integer $M\ge2$.