pythonで全探索generator

Atcoderで使うことを想定してつくったので、python3.8です。3.9ならtyping.List[T]じゃなくてlist[T]で済みます。早くpythonの型付けも洗練されるとうれしいですね。

from typing import List
T = TypeVar("T")


def ES(seq: List[T]):
    """exhaustive search"""
    if(len(seq) == 1):
        yield []
        yield seq
    else:
        head, rest = seq[0], seq[1:]
        for cand in ES(rest):
            yield cand
            yield [head] + cand


for c in ES([1, 2, 3, 4]):
    print(c)
    # []
    # [1]
    # [2]
    # [1, 2]
    # [3]
    # [1, 3]
    # [2, 3]
    # [1, 2, 3]
    # [4]
    # [1, 4]
    # [2, 4]
    # [1, 2, 4]
    # [3, 4]
    # [1, 3, 4]
    # [2, 3, 4]
    # [1, 2, 3, 4]