LeetCode - 括号生成

这是一月多以前做的一题中等难度的题目，题目是第22题，一遍过。

原题地址： https://leetcode-cn.com/problems/generate-parentheses/

题目描述：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/generate-parentheses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这题的话想法比较简单：

1. 确定好最终结果的最大可能大小，然后新建List，减少List扩容的机会
2. 新建一个递归函数，入参为当前的括号集合、括号字符串、剩余左括号数量和右括号的数量
3. 如果没有剩余的括号了，则将当前字符串添加到List中后返回
4. 如果还有左括号，就加一个左括号；有右括号就加一个右括号。

递归调用的情况下，这题和之前的求子集的题类似。

中文官网题解：

https://leetcode-cn.com/problems/generate-parentheses/solution/

个人题解：

class Solution {
public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>((int) Math.pow(2, n));
        generate(list, "", n, n);
        return list;
    }

    private void generate(List<String> list, String str, int l, int r) {
        if (l == 0 && r == 0) {
            list.add(str);
            return;
        }
        if (l > 0) {
            generate(list, str + '(', l - 1, r);
        }
        if (r > l) {
            generate(list, str + ')', l, r - 1);
        }
    }
}

结果：

从结果上来看，运行效率还算不错。