Lesson 3

In a valid parenthesis sequence, the first parenthesis must be an opening one. It must be matched by a closing parenthesis somewhere (it can appear immediately after the opening one or at the very end; the balance of the corresponding prefix is zero). So, our sequence looks like this: \[\texttt{(L)R}\ .\] This simple observation helps us generate valid parenthesis sequences. It remains to note that both \(\texttt{L}\) and \(\texttt{R}\) must be valid parenthesis sequences.

from itertools import product


def bracket_sequences(n):
    if not n:
        yield ''
    else:
        for k in range(n):
            for left, right in product(bracket_sequences(k), bracket_sequences(n - k - 1)):
                    yield f'({left}){right}'

print(*bracket_sequences(3))

()()() ()(()) (())() (()()) ((()))