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:
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:
