Source code for tryalgo.subsetsum_divide

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Subsetsum by splitting

christoph dürr et jill-jênn vie - 2014-2019
"""


# snip{


def part_sum(x_table, i=0):
    """All subsetsums from x_table[i:]

    :param x_table: table of values
    :param int i: index_table defining suffix_table of x_table to be considered
    :iterates: over all values, in arbitrary order
    :complexity: :math:`O(2^{len(x_table)-i})`
    """
    if i == len(x_table):
        yield 0
    else:
        for s_idx in part_sum(x_table, i + 1):
            yield s_idx
            yield s_idx + x_table[i]





def subset_sum(x_table, r_target):
    """Subsetsum by splitting

    :param x_table: table of values
    :param r_target: target value
    :returns bool: if there is a subsequence of x_table with total sum r_target
    :complexity: :math:`O(n^{\\lceil n/2 \\rceil})`
    """
    k = len(x_table) // 2              # divide input
    y_value = list(part_sum(x_table[:k]))
    z_value = [r_target - v for v in part_sum(x_table[k:])]
    y_value.sort()       # test of intersection between y_value and z_value
    z_value.sort()
    i = 0
    j = 0
    while i < len(y_value) and j < len(z_value):
        if y_value[i] == z_value[j]:
            return True
        if y_value[i] < z_value[j]:  # increment index of smallest element
            i += 1
        else:
            j += 1
    return False

# snip}


# snip{ subset_sum2


def part_sum2(x_table):
    """All subsetsums from a list x

    :param x_table: list of values
    :complexity: :math:`O(2^{len(x)})`
    """
    answer = set([0])        # 0 = value of empty set
    for xi in x_table:
        answer |= set(value + xi for value in answer)
    return answer





def subset_sum2(x_table, r_target):
    """Subsetsum by splitting

    :param x_table: table of values
    :param r_target: target value
    :returns bool: if there is a subsequence of x_table with total sum r_target
    :complexity: :math:`O(n^{\\lceil n/2 \\rceil})`
    """
    k = len(x_table) // 2              # divide input
    y_set = part_sum2(x_table[:k])
    z_set = set(r_target - value for value in part_sum2(x_table[k:]))
    return len(y_set & z_set) > 0        # test intersection

# snip}