Scamming the coding interview: Problem 006: Partition into sets of equal sum

partition_sets_of_equal_sum.py

"""
Scamming the coding interview
"""

def generate_all_combinations(nums, combinations, start_index, running_set):
    """
    Generates all the combinations a given list of numbers
    """
    if start_index >= len(nums):
        return

    for i, num in enumerate(nums):

        if i < start_index:
            continue

        temp_comb = running_set[:]
        temp_comb.append(num)
        combinations.append(temp_comb)

        generate_all_combinations(nums, combinations, i + 1, temp_comb)


def find_parts(nums):
    """
    Splits the given numbers list into sets such that the sum of both the sets is same
    """
    length_of_num = len(nums)
    a = nums[0:length_of_num]
    b = nums[length_of_num:]

    total_sum = sum(nums)

    half_sum = total_sum/2

    a_combinations = []
    generate_all_combinations(a, a_combinations, 0, [])

    a_sum_to_combination_map = {}

    answer = None

    for combination in a_combinations:
        temp_s = sum(combination)
        a_sum_to_combination_map[temp_s] = combination
        if temp_s == half_sum:
            answer = combination
            break

    b_combinations = []
    generate_all_combinations(b, b_combinations, 0, [])

    for combination in b_combinations:
        temp_s = sum(combination)

        if temp_s == total_sum/2:
            answer = combination
            break

        needed = total_sum/2 - temp_s

        if a_sum_to_combination_map.get(needed):
            answer = combination + a_sum_to_combination_map.get(needed)

    if answer:
        first_set = answer[:]
        nums_copy = nums[:]
        for n in answer:
            nums_copy.remove(n)
        second_set = nums_copy
        return first_set, second_set
    else:
        return None, None


if __name__ == '__main__':

    s = [15, 5, 15, 10, 10, 20, 35]
    a, b = find_parts(s)

    print(a)
    print(b)