Sequenze di parentesi
Dato un intero positivo
n, genera tutte le sequenze di parentesi valide di dimensione 2n e stampale in ordine lessicografico.La definizione di una sequenza di parentesi valida è la seguente:
- Una stringa vuota è una sequenza di parentesi valida.
- Se
Sè una sequenza di parentesi valida, allora(S)è anch’essa una sequenza di parentesi valida.
- Se
AeBsono sequenze di parentesi valide, alloraABè anch’essa una sequenza di parentesi valida.
Input
L’input consiste di un singolo intero
n (1 ≤ n ≤ 11).Output
Stampa tutte le sequenze di parentesi valide di dimensione
2n, ognuna su una riga separata. Le sequenze devono essere stampate in ordine lessicografico.Esempi
Ingresso | Uscita |
3 | ((()))
(()())
(())()
()(())
()()() |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 7 MB