学了一点形式语言与自动机，于是就想着用生成的方法来写一个。思路应该和老师说的归纳法类似。

假设S，T是合法的串，于是有两种生成规则（注意判断长度不能超过n*2）：


1. concat: S + T
2. expand: '(' + S + ')'

每轮循环从已有的串中取出串并应用以上两种规则，把生成的新串添加到集合中，直至集合的规模不再增大，算法收敛。

取出集合中长度为n*2的串作为结果即可。
提交可以通过，用时200MS+
这个复杂度不知道怎么分析了。超哥有想法吗？

```processing
public class GenerateParentheses {
    String concat(String s1, String s2) {
        return s1 + s2;
    }
    String expand(String s) {
        return "(" + s + ")";
    }

    HashSet<String> set = new HashSet<>();
    public List<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<>();
        if (n < 1) return result;
        int cnt = set.size();
        set.add("()");
        while (cnt < set.size()) { // 尚未收敛
            cnt = set.size();
            HashSet<String> frontier = new HashSet<>(); // 此轮新生成的序列
            for (String s1: set) {
                if (s1.length() < n * 2) frontier.add(expand(s1));
                for (String s2: set) {
                    if (s1.length() + s2.length() <= n * 2) frontier.add(concat(s1, s2));
                }
            }
            set.addAll(frontier); // 合并新旧集合。如果有新元素加进来，则会进入下一次循环
        }
        for (String s: set) {
            if (s.length() == n * 2) result.add(s);
        }
        return result;
    }
}
```