2-partition problem

Having a list of integers, we want to know if we can split it evenly in two parts.

There is a well known, elegant and relatively fast dynamic programming solution to this problem.

Say that this is the list

[3, 1, 1, 2, 2, 1]

Being the sum of its elements ten, we'll have a positive answer to the problem if we could find a subcollection with a sum of five.

To check it, we build a table having rows from zero to the sum of the subcollection we are looking for - five in this case. Actually, the zeroth row is pretty useless here, I keep it just because it makes indices less confusing in the code. The columns represents the partial sum of elements in the list we have in input, column zero is for the empty collection, one contains just the first element (3 in the example), column two the first two items (3 and 1 here), up to the last one that keep all.

The content in each cell is the answer to the question: is there a combination of elements in the subcollection specified by the column that have a sum specified by the row?

So, for instance, table[2][3] means: could I get 2 as a sum from [3, 1, 1]? The answer is yes, because of latter two elements.

The bottom-right cell in the table is the answer for the original problem.

Let's construct the table. Whatever I put in the topmost row is alright, since I won't use it in any way. They would represent the answer to the question if I could get a sum zero from a collection that could be empty (leftmost cell) up to including all the element in the original input (rightmost cell). Logically, we should put a True inside each of them but, since we don't care, I leave instead a bit misleading False. Forgive me, but this let me initialize with more ease the table, considering that each first cell in any row (but the zeroth one) should be initialized with False, since it is impossible having a sum different from zero from an empty collection.

Now let's scan all the cell in the table, from (1, 1) to the bottom-right one, moving from left to right, row by row.
If the currently added element in the list has the same value of the row index (that is, the total we are looking for), we can put a True in it.
If the cell on the immediate left contains a True, we can, again, safely put a True in it. Adding an element to the collection won't change the positive answer we already get.
If the first two checks don't hold, I try to get the total adding up the current value to the previous one. If so, bang, True again.

At the end of looping, we should get a table like the one shown here below.

(a) The cell (1, 2) is set to True because the column represent the subcollection {3,1}, having as latest element the row index.
(b) The cell (1, 4) is True because (1, 3) is True
(c) The cell (4, 2) is True because of cell (3, 1), checked because being the left adjacent column, moving up 1 (from the latest element in current subcollection {3,1}).

Checking the bottom-right cell we have a True, so the answer to our original question is yes.

Here is my python implementation of this algorithm:

def solution(values):
    total = sum(values)  # 1
    if total % 2:
        return False

    half = total // 2
    table = [[False] * (len(values) + 1) for _ in range(half + 1)]  # 2

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

    return table[-1][-1]  # 6

1. If the sum of values is not an even number, we already know that the list can't be split evenly.
2. Build the table as described above. Don't pay attention to the topmost row, it's just a dummy.
3. Loop on all the "real" cell, skipping the leftmost ones, that are left initialized to False.
4. See above, case (a) and (b) as described and visualized in the picture
5. This code implements the case (c). I get the the tentative row index in ii. If the relative cell on the left adjacent column is available and it is set to True, the current cell is set to True too.
6. Get the solution to the problem.

I pushed my python code and a few test cases on GitHub.