unreasonably effective

from itertools import product as cartesian

class Solution:
    # No need to keep track of visited bits, because:
    #   1. Bits are unique in allowed_bits
    #   2. We scan unidirectionally: left to right
    def generate_half(
        self,
        nbit: int,
        index: int,
        current_bits: List[int],
        halves: Set[str],
        max_val: int,
        expected_digit_count: int,
        allowed_bits: List[int],
    ) -> None:

        if len(current_bits) == nbit:
            val = sum(current_bits) if current_bits else 0
            if val > max_val:
                return
            val_str = str(val)
            padding_count = expected_digit_count - len(val_str)
            val_str = ("0" * padding_count) + val_str
            halves.add(val_str)
            return

        if index >= len(allowed_bits):
            return

        # Skip current bit
        self.generate_half(
            nbit,
            index + 1,
            current_bits,
            halves,
            max_val,
            expected_digit_count,
            allowed_bits,
        )

        # Take current bit
        self.generate_half(
            nbit,
            index + 1,
            current_bits + [allowed_bits[index]],
            halves,
            max_val,
            expected_digit_count,
            allowed_bits,
        )

    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        max_hour_bit_count, max_minute_bit_count = 4, 6
        hour_bits = [1 << i for i in range(max_hour_bit_count)]
        minute_bits = [1 << i for i in range(max_minute_bit_count)]
        max_hour_val, max_minute_val = 11, 59
        expected_hour_digit_count, expected_minute_digit_count = 1, 2

        times = []
        for turned_on_hour_bit_count, turned_on_minute_bit_count in cartesian(
            range(max_hour_bit_count), range(max_minute_bit_count)
        ):
            if turned_on_hour_bit_count + turned_on_minute_bit_count != turnedOn:
                continue

            hours = set()
            self.generate_half(
                turned_on_hour_bit_count,
                0,
                [],
                hours,
                max_hour_val,
                expected_hour_digit_count,
                hour_bits,
            )

            minutes = set()
            self.generate_half(
                turned_on_minute_bit_count,
                0,
                [],
                minutes,
                max_minute_val,
                expected_minute_digit_count,
                minute_bits,
            )

            # If one of the iterables is empty, the cartesian product is empty
            times.extend(h + ":" + m for h, m in cartesian(hours, minutes))

        return times