balanced_partition_python.py

# Author: manu.datta@gmail.com
# balanced partition problem
def solution(A):
    a = list(map(abs,A)) # specific to codility problem 
    L = len(a)
    if L == 1:
        return a[0] 
    array_sum = sum(a)
    half,m = divmod(array_sum,2)
    #print(half,m)
    half += m
    nearest_knapsack = [0 for _ in range(half+1)]
    nearest_knapsack[0] = 1 # 0 length can always be made
    #print(half)
    for k in a:
        if m == 0 and nearest_knapsack[-1] == 1:
            return 0
        for i in range(half,k-1,-1):
            aik = (nearest_knapsack[i-k] == 1)
            # if we have 1 at (i-k) we can jump to i using k
            #print("if we have 1 {} at (i-k)={} we can jump to i={} using k={}".format(aik,(i-k),i,k))
            #print(i-1,",",k)
            if aik:
                nearest_knapsack[i] = 1
    nearest_sum_to_half = half
    while nearest_sum_to_half >=0 :
        if nearest_knapsack[nearest_sum_to_half] == 1:
            break
        nearest_sum_to_half = nearest_sum_to_half-1;
    rest = array_sum - nearest_sum_to_half
    return abs(rest - nearest_sum_to_half)