Partitioning problem: Arbitrary list of integers of any length and in any order Determine if the list is partitionable or not. A partitioned list is one where it can be split into 2 lists with equal sum. Enumerate the list of cases to solve to minimize execution time and provide the Order of the algorithm Provide code showing the implementation …

balanced_partition.py

from functools import reduce


def is_balanced_partition(arr):

    total = reduce(lambda x, y: x+y , arr)

    if total % 2 != 0:
        return False

    half_total = int(total / 2)

    arr_len = len(arr)

    partition = [[None]*(arr_len+1) for i in range(half_total+1)]

    for i in range(0, arr_len + 1):
        partition[0][i] = True

    for i in range(1, half_total + 1):
        partition[i][0] = False

    for i in range(1, half_total + 1):
        for j in range(0, arr_len + 1):
            partition[i][j] = partition[i][j-1]
            if i >= arr[j-1]:
                partition[i][j] = partition[i][j] or partition[i - arr[j-1]][j-1]

    return partition[half_total][arr_len]

if __name__ == '__main__':

    arr = [1, 1, 1, 3]
    print(is_balanced_partition(arr))