partitioning.py

import sys

if sys.version_info[0] >= 3:
    xrange = range


def list_partitate(elems):
    if not isinstance(elems, list):
        return False

    count = len(elems)
    summ = sum(elems)

    if summ % 2 != 0:
        return False

    # creating matrix
    # with initialized top rows that will be always true
    p_table = [
        [True for i in xrange(count + 1)]
        for j in xrange(summ // 2 + 1)
    ]

    # intialize leftmost column, skip starting top point
    for i in xrange(1, summ // 2 + 1):
        p_table[i][0] = False

    # start fill table from bottom to down
    for i in xrange(1, summ // 2 + 1):

        for j in xrange(1, count + 1):
            p_table[i][j] = p_table[i][j - 1]

            if i >= elems[j - 1]:
                p_table[i][j] = p_table[i][j] or p_table[i - elems[j - 1]][j - 1]

    return p_table[summ // 2][count]


elems1 = [1, 2, 3, 4, 5, 6, 7]
elems2 = [1, 10, 5, 21, 4]
elems3 = [1, 10, 5, 21, 4, 1]
elems4 = [1, 21, 500, 40]

assert list_partitate(elems1) is True
assert list_partitate(elems2) is False
assert list_partitate(elems3) is True
assert list_partitate(elems4) is False