鲁迅说过，每天刷一道二哥的 LeetCode 题解，感觉精神百倍，工作效率都提高了（dog）。

题意

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

• 1 <= n <= 8

难度

中等

示例

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

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

分析

什么是有效的括号？例如：

String: "(  (  (  )  )  )"
位置     :1  2  3  4  5  6
左括号数量:1  2  3  3  3  3
右括号数量:0  0  0  1  2  3

再例如：

String: "(  (  )  (  )  )"
位置     :1  2  3  4  5  6
左括号数量:1  2  2  3  3  3
右括号数量:0  0  1  1  2  3

我们发现，无论在哪个位置，右括号数量都是小于等于左括号的，并且当左括号数量小于 n 时，我们可以无限添加左括号，对吧？

当右括号数量小于左括号数量时，我们可以无限添加右括号。

当括号的数量达到 2n 时，我们就得到了所有的有效括号。

当我们把括号的问题转化成树结构的时候，就可以更直观地理解这个问题。在数结构中，每个节点代表一个括号组合。

从根节点（空字符串）开始，每一层代表字符串中添加新括号的操作。对于每个节点，它最多可以有两个子节点：

• 一个代表添加一个左括号(，如果添加后不超过 n 个左括号
• 另外一个代表添加一个右括号)，如果添加后右括号数量小于左括号数量

每一层都比前一层有更多可能的括号组合，等到达到 2n 时，所有路径都是有效的括号组合。

假设 n = 2 时，我们可以得到如下的树结构：

• 在这个树中，根节点是空字符串 ""。
• 第一层有一个节点 "("，代表我们添加可以一个左括号。X 表示我们不能添加右括号。
• 第二层展示了添加第二个括号时的所有可能性：我们可以再添加另外一个左括号 "("（左括号数量小于 n），或者添加一个右括号 ")"（右括号数量小于左括号数量）。
• 以此类推，我们可以得到所有的有效括号组合。

class Solution {
    List<String> combinations = new ArrayList<>();
    // 主方法，调用此函数生成所有的括号组合
    public List<String> generateParenthesis(int n) {
        backtrack("", 0, 0, n);
        return combinations;
    }

    // 回溯方法
    private void backtrack(String current, int open, int close, int max) {
        // 如果当前字符串长度等于最大长度的两倍，说明找到了一个解，添加到结果列表中
        if (current.length() == max * 2) {
            combinations.add(current);
            return;
        }

        // 如果左括号数量小于 n，可以添加一个左括号
        if (open &l