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

Thanks!

ReplyDeleteThank you for the solution.

ReplyDeleteThank you for your feedback!

ReplyDeleteThank you very much for sharing this! This helped me a lot!

ReplyDeleteMy pleasure :)

DeleteThx for your solution!

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

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.

DeleteThank 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?

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

DeleteHi, 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?

ReplyDeletethx

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.

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