Partitioning Souvenirs

Given a list of integers, we want to know if there is a way to split it evenly in three parts, so that the sum of each part is the same than the other ones.

Problem given in week six of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.

This 3-partition problem is not too different from the classic 2-partition one, for which I have described the well known dynamic programming solution in the previous post. As before, we build a table where the rows represents the sums we want to get and the columns the elements in the collection we are about to consider.
However, we have to change a bit the meaning of the value that we push in each cell. This time we check two of the three tentative subcollections, and we want to keep track of how many of them could have as sum the row index, given the elements of the input list available in that column.

Consider as example this input:

[3, 1, 1, 2, 2]

We are looking for three subcollections having all a sum of three. The table is having six columns and four rows, including a first dummy one. We initialize all its cells to zero, and we loop on all the "real" cells applying rules close to the ones we have seen for the 2-partition problem, with slight variations.
(a) If the column element matches the row index, I increase the value of the left-hand cell, up to reach 2.
(b) If there is not a match, but the column element added to the previous one matches it, I still increase the value of the left-hand cell, up to reach 2.
(c) Otherwise, I copy the value in the left-hand cell to the current one.
The result should be reflected by this table:

And the answer to the original question is yes only if the bottom-left value in the table is two.

Here is my python code to implement this algorithm.

def solution(values):
    total = sum(values)
    if len(values) < 3 or total % 3:  # 1
        return False
    third = total // 3
    table = [[0] * (len(values) + 1) for _ in range(third + 1)]  # 2

    for i in range(1, third + 1):
        for j in range(1, len(values) + 1):  # 3
            ii = i - values[j - 1]  # 4
            if values[j - 1] == i or (ii > 0 and table[ii][j - 1]):  # 5
                table[i][j] = 1 if table[i][j - 1] == 0 else 2
            else:
                table[i][j] = table[i][j - 1]  # 6

    return True if table[-1][-1] == 2 else False

1. If dividing the sum of values by three I get a remainder, or if there are less than three elements in the list, for sure there is no way of 3-partition my list.
2. Build the table as discussed above. Note the zero as default value, even in the dummy top row - it is not formally correct, but those values are not used anywhere.
3. Loop on all the "real" cells.
4. Precalculate the row for the (b) check described above.
5. The first part of the condition is the (a) check above. If it fails, we pass to the second part, using the row calculate in (4). If one of the two conditions is true, the value of the current cell is increased up to 2.
6. Vanilla case, moving to the right we keep the value already calculate for the previous cell.

It looks easy, once one see it, doesn't it?

Actually, a tad too easy, as Shuai Zhao pointed out - see below in the comments. The problem is that the (b) check, as described above, is too simple. Before using a value I have to ensure it has not already used on the same line. Things are getting complicated, better to explain them in another post.

I pushed my python code and a few test cases to GitHub. The latest version is the patched code, working also for the Shuai test. Get back in the history if you want to see the solution described here.