Algorithmen und Datenstrukturen

Klammersequenzen

Gegeben ist eine positive ganze Zahl n. Es sollen alle gültigen Klammersequenzen der Länge 2n erzeugt und in lexikografischer Reihenfolge ausgegeben werden.
Die Definition einer gültigen Klammersequenz lautet wie folgt:
  • Eine leere Zeichenkette ist eine gültige Klammersequenz.
  • Ist S eine gültige Klammersequenz, dann ist (S) ebenfalls eine gültige Klammersequenz.
  • Sind A und B gültige Klammersequenzen, dann ist AB ebenfalls eine gültige Klammersequenz.

Eingabe

Die Eingabe besteht aus einer einzigen ganzen Zahl n (1 ≤ n ≤ 11).

Ausgabe

Geben Sie alle gültigen Klammersequenzen der Länge 2n aus. Jede Sequenz wird in einer eigenen Zeile ausgegeben. Die Reihenfolge der Ausgaben sollte lexikografisch sein.

Beispiele

Eingabe
Ausgabe
3
((())) (()()) (())() ()(()) ()()()

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 7 MB

To check your solution you need to sign in
Sign in to continue