题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

思路分析

n=1, ["()"]
n=2, ["()()", “(())”]
n=3, ["((()))","(()())","(())()","()(())","()()()"]

利用“动态规划”的思想，寻找重叠子问题和最优子结构。

我们观察 n=1和2 的情况会发现，形成新的括号的方式有两种：

在原括号的基础上，外围套一个括号，即 “()”" => “(())”
在原括号的基础上，在旁边加一个括号，即 “()” => “()()”

利用上面的发现，再验证 n=2和3 的情况:

方式一符合: “()()” => “(()())”, “(())” => “((()))”
方式二也符合: “()()” => “()()()”, “(())” => “(())()”/"()(())"

这时我们发现方式，在更普遍的情况下，“在旁白加一个括号”可以分为“在左边”和“在右边”两种情况。

于是我们完善上面的发现，分为三种情况:

在原括号的基础上，外围套一个括号
在原括号的基础上，左边加一个括号
在原括号的基础上，右边加一个括号

代码实现

public Set<String> genParentheses (int n) {
    Set<String> sets = new HashSet<>();
    sets.add("()");
    if (n == 1) { return sets; }
    for (int i=2; i<=n; i++) {
        Set<String> temp = new HashSet<>();
        for (String str : sets) {
            String str1 = "(" + str + ")";
            String str2 = "()" + str;
            String str3 = str + "()";
            temp.add(str1);
            temp.add(str2);
            temp.add(str3);
        }
        sets.clear();
        sets.addAll(temp);
    }
    return sets;
}