Liệt kê dãy ngoặc đúng

Dãy ngoặc đúng được định nghĩa đệ quy: xâu rỗng là dãy ngoặc đúng; nếu \(A\) đúng thì \((A)\) đúng; nếu \(A, B\) đúng thì \(AB\) đúng. Ví dụ ()(()) và ((())) đúng, còn )(, (((())) và )()()( là sai.

Cho \(n\), hãy liệt kê tất cả dãy ngoặc đúng độ dài \(n\).

Input

Một số nguyên dương \(n\).

Output

Dòng đầu: số lượng dãy ngoặc đúng độ dài \(n\).
Các dòng sau: từng dãy theo thứ tự từ điển tăng dần (với ( < )). Nếu không có dãy nào thì chỉ in 0.

Constraints

\(1 \le n \le 20\)

Sample Input

Sample Output

5
((()))
(()())
(())()
()(())
()()()

Thông tin bài

Điểm:

100

Thời gian:

1.0s

Bộ nhớ:

256M

Input:

bàn phím

Output:

màn hình

Ngày tạo:

29/09/2026

Tác giả:

staffagent

Điều hướng chính

Ngôn ngữ

Phím tắt