def METHOD_NAME(read_set, all_heterozygous):
    """Solves MEC by enumerating all possible bipartitions."""
    def print(*args):
        pass
    assert len(read_set) < 10, "Too many reads for brute force"
    positions = read_set.get_positions()
    if all_heterozygous:
        possible_assignments = [(0, 1), (1, 0)]
    else:
        possible_assignments = [(0, 0), (0, 1), (1, 0), (1, 1)]
    # bit i in "partition" encodes to which set read i belongs
    best_partition = None
    best_cost = None
    best_haplotypes = None
    solution_count = 0
    for partition in range(2 ** len(read_set)):
        print(f"Looking at partition {partition:0>{len(read_set)}b}")
        # compute cost induced by that partition
        cost = 0
        haplotypes = []
        for p in positions:
            # find variants covering this position
            variants = [[], []]
            for n, read in enumerate(read_set):
                i = (partition >> n) & 1
                for variant in read:
                    if variant.position == p:
                        variants[i].append(variant)
            c, assignment = column_cost(variants, possible_assignments)
            print(f"    position: {p}, variants: {str(variants)} --> cost = {c}")
            cost += c
            haplotypes.append(assignment)
        print("  --> cost for this partitioning:", cost)
        if (best_cost is None) or (cost < best_cost):
            best_partition = partition
            best_cost = cost
            best_haplotypes = haplotypes
            solution_count = 1
        elif cost == best_cost:
            solution_count += 1
    # Each partition has its inverse with the same cost
    assert solution_count % 2 == 0
    haplotype1 = "".join([str(allele1) for allele1, allele2 in best_haplotypes])
    haplotype2 = "".join([str(allele2) for allele1, allele2 in best_haplotypes])
    return (
        best_cost,
        [(best_partition >> x) & 1 for x in range(len(read_set))],
        solution_count // 2,
        haplotype1,
        haplotype2,
    )