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.

11 comments:

  1. Thank you for your feedback!

    ReplyDelete
  2. Thank you very much for sharing this! This helped me a lot!

    ReplyDelete
  3. Thx for your solution!
    When I try to solve this problem
    https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
    I find a wrong case [7, 2, 2, 2, 2, 2, 2, 2, 3]
    The right answer is False, but the code return True.

    ReplyDelete
    Replies
    1. the cell (2, {7,2,2}) is 2, the cell (4, {7,2,2}) is 1, so the code get cell (4, {7,2,2,2}) is 2, but it should be 1.

      Delete
    2. Thank you for you useful comment, Shuai. You are right, my solution is not correct. Your test case shows how I forgot to consider that we should ensure an element is not used more than once to generate a sum. I wonder if I could save this algorithm keeping track if an element is free or already taken. Or, do you have a better idea?

      Delete
    3. I have patched the code following the spark of keeping track of taken items. The resulting code is on GitHub and it is described in this other post.

      Delete
  4. Hi, first of all, thanks for ur solution and it helps me a lot. However, there is a question I wanna ask: What does "2" really means in this solution?
    thx

    ReplyDelete
    Replies
    1. Thank you for your question. Please, also have a look at the comment above from Shuai Zhao for a warning on this solution, that I patched and discussed in this other post.
      I guess you are asking what means "2" in the table, right? As you could see in line #2, each cell is initialized to 0, then the line #5 checks if it is the case of setting a specific cell value to 1 or 2.
      The idea is that each cell is keeping track of the number of times we could get 'x' (the row index) from the elements identified by 'y'. We count only up to 2, because 3 - the value that we are actually looking for - is implicit by the construction of the problem.
      So, for instance:
      - the value for cell x = 1, y = {3} is 0, since we could not get 1 from {3}
      - the value for x = 1, y = {3, 1} is 1, since we could get a single 1 from {3, 1}
      - the value for x = 1, y = {3, 1, 1} is 2, since we could get two 1's from {3, 1, 1}
      And, we return True since in x = 3, y = {3, 1, 1, 2, 2} there is a 2, meaning that we could get _at least_ two 3's. That, as said above, here means three, for how the solution is designed.

      Delete