import time


############################################################
# pruning in decision trees
############################################################


def subsets_with_size(items, size):
    # base case
    if len(items) == 0:
        if size == 0:
            return [set()]
        else:
            return []

    # pruning
    if size == 0:
        return [set()]

    # recursive decomposition
    first, rest = items[0], items[1:]

    # all subsets without first
    combos_without = subsets_with_size(rest, size)

    # all subsets with first
    combos_with = [
        {first} | combo
        for combo in subsets_with_size(rest, size - 1)
    ]

    return combos_without + combos_with


def test_subset_size():
    max_num_items = 5
    subset_size = 2

    for k in range(1, max_num_items + 1):
        print(f"generating subsets from {k} items")
        sequence = list(range(1, k + 1))
        result = subsets_with_size(sequence, subset_size)
        if k < 10:
            print(result)


print()
test_subset_size()


def subsets_in_size_range(items, size_range):
    lower, upper = size_range

    # base case
    if len(items) == 0:
        if ...:  # TODO
            return [set()]
        else:
            return []

    # pruning
    if ...:  # TODO
        return [set()]

    # recursive decomposition
    first, rest = items[0], items[1:]

    # all subsets without first
    combos_without = ...  # TODO

    # all subsets with first
    combos_with = ...  # TODO

    return combos_without + combos_with


def test_subset_size_range():
    max_num_items = 5
    subset_size_range = 1, 2

    for k in range(1, max_num_items + 1):
        print(f"generating subsets from {k} items")
        sequence = list(range(1, k + 1))
        result = subsets_in_size_range(sequence, subset_size_range)
        if k < 10:
            print(sorted(result, key=len))


print()
test_subset_size_range()