括号

给定一个整数 n。生成所有长度为 n 的合法括号序列，并按字典序升序输出。合法括号序列定义：

（1）空字符串是合法的；

（2）若字符串 s 合法，则 (+s+) 合法；

（3）若字符串 s 和 t 合法，则 s+t 合法。

时间限制：1000ms内存限制：256MB

输入格式

输入一个整数n。

输出格式

每行输出一个合法括号序列（按字典序升序）。若无解则不输出。

输入样例#1

2

输出样例#1

()

输入样例#2

4

输出样例#2

(())
()()

输入样例#3

6

输出样例#3

((()))
(()())
(())()
()(())
()()()

数据范围：

1≤N≤20，N 是偶数。

这个问题可以通过递归的方式解决。具体思路如下：

1. 当n=1时，输出"(“和”)"。
2. 当n>1时，对于每一个左括号"(“，递归生成剩余n-1个括号的所有可能序列，然后在每个序列前加上”(“。同时，对于每一个右括号”)“，递归生成剩余n-1个括号的所有以”)"结尾的序列。最后将这两类序列合并并去重，即为长度为n的所有合法括号序列。

以下是C语言的实现代码：

#include <stdio.h>
#include <string.h>

void generateParenthesis(int n, int left, int right, char *s, int *pos) {
    if (left == n && right == n) { // 达到括号平衡且生成完所有括号，输出序列
        printf("%s\n", s);
        return;
    }
    if (left < n) { // 还可以添加左括号
        s[*pos] = '('; // 添加左括号
        generateParenthesis(n, left + 1, right, s, pos + 1); // 递归生成剩余括号序列
    }
    if (right < left) { // 添加右括号的前提是右括号数量小于左括号数量
        s[*pos] = ')'; // 添加右括号
        generateParenthesis(n, left, right + 1, s, pos + 1); // 递归生成剩余括号序列
    }
}

int main() {
    int n;
    scanf("%d", &n);
    char s[40]; // 存储生成的括号序列，长度为2n，因为最多有n个左括号和n个右括号，中间需要加一个结束符'\0'
    memset(s, 0, sizeof(s)); // 初始化序列为全零字符（方便后续判断是否已经访问过）
    generateParenthesis(n, 0, 0, s, 0); // 从空序列开始生成长度为n的合法括号序列
    return 0;
}