#!/usr/bin/python



def find_combos(sizes, taken, avail, remaining):
    result = set()

    # For each container we haven't used yet
    for i in avail:
        # If its capacity is less than what we need, recurse to find
        # containers for the remaining liquid, which might not succeed.
        if sizes[i] < remaining:
            _taken = taken | {i}
            _avail = avail - {i}
            _remaining = remaining - sizes[i]
            for c in find_combos(sizes, _taken, _avail, _remaining):
                result |= {frozenset([i]) | c}
        # If its capacity is exactly what we need, we've found an option
        elif sizes[i] == remaining:
            result |= {frozenset([i])}
        # If its capacity is too large, this isn't an option; continue

    return result



def solve_partn(partn, combos):
    if partn == 1:
        options = combos
    else: # partn == 2
        lengths = map(len, combos)
        min_len = min(lengths)
        options = {c for c in combos if len(c) == min_len}
    return len(options)



def main():
    # Read container volumes from the input text file
    with open("input.txt", "r") as f:
        sizes = list(map(int, f.read().splitlines()))

    # Extremely expensive (takes several minutes), so do it once up front
    combos = find_combos(sizes, set(), set(range(len(sizes))), 150)

    print("Part 1 solution:", solve_partn(1, combos)) # 1304 for me
    print("Part 2 solution:", solve_partn(2, combos)) #   18 for me



if __name__ == "__main__":
    main()