题目

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

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

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

思路分析

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

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

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

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

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

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

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

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

  1. 在原括号的基础上,外围套一个括号
  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;
}