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

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

回溯算法，因为要合法，所以最初必须是放左括号开始。题目要求n代表括号的对数，那么就一共有n个左括号，n个右括号。根据这个思想，就可以编写递归函数。

最初总共有n个左括号，n个右括号，先放一个左括号，然后做选择，回溯，再放右括号。递归函数的判定条件是：由于先放左括号，所有左括号的数量是一直小于等于右括号的，出现左大于右，不合法，返回。如果左右括号数量小于0，不合法返回。当数量都为0，说明满足条件。

class Solution {
    public List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        StringBuilder track = new StringBuilder();
        // 回溯算法
        backTrace(n, n, track);

        return res;
    }

    // 剩余左右括号数都为n
    public void backTrace(int countLeft, int countRight, StringBuilder track) {
        // 剩余左括号数大于剩余右括号不合法，返回
        if (countLeft > countRight) return;
        // 剩余括号数小于0不合法，返回
        if (countLeft < 0 || countRight < 0) return;
        // 当剩余左右括号数都为0，满足条件
        if (countLeft == 0 && countRight == 0) {
            res.add(track.toString());
            return;
        }

        // 放入左括号
        track.append('(');
        // 进入下一层
        backTrace(countLeft - 1, countRight, track);
        // 回溯
        track.deleteCharAt(track.length() - 1);

        // 放入右括号
        track.append(')');
        // 进入下一层
        backTrace(countLeft, countRight - 1, track);
        // 回溯
        track.deleteCharAt(track.length() - 1);
    }
}

结果如下：