Problem - De Bruijn Sequence

Problem: Given $n$, construct a minimum-length bit string that contains every $n$-bit string as a substring.

Link: CSES 1692

Constraints: $1 \leq n \leq 15$

Output: A bit string of length $2^n + n - 1$ (the De Bruijn sequence).

Example: For $n = 2$, output "$00110$" (length $5 = 4 + 2 - 1$). Build a directed graph where nodes are $(n-1)$-bit strings and edges represent $n$-bit strings. Find an Euler circuit on this graph.