C. LKBRACKET - Sinh các dãy ngoặc đúng

Xét dãy ngoặc là một xâu chỉ gồm các ký tự ( và ). Ta định nghĩa dãy ngoặc đúng như sau:

• Xâu rỗng là một dãy ngoặc đúng.
• là một dãy ngoặc đúng khi và chỉ khi có một trong hai dạng: hoặc trong đó là các dãy ngoặc đúng.

Cho số nguyên dương , hãy liệt kê tất cả các dãy ngoặc đúng độ dài .

Dữ liệu vào:

• Một dòng duy nhất chứa số nguyên dương .

Dữ liệu ra:

• Liệt kê tất cả các dãy ngoặc đúng độ dài theo thứ tự từ điển tăng dần (theo nguyên tắc so sánh chuỗi, chú ý ( < ) ), mỗi dãy trên một dòng

Ví dụ:

Dữ liệu vào:

2

Dữ liệu ra:

(())
()()

Giải thích:

• Với bằng , chỉ có dãy ngoặc đúng độ dài theo thứ tự như trên.

Giới hạn:

• .