算法

(递归)

通过观察我们可以发现，生成的任何括号组合中都有两个规律：

1. 括号组合中左括号的数量等于右括号的数量
2. 括号组合中任何位置左括号的数量都大于等于右括号的数量

第一条很容易理解，我们来看第二条，比如有效括号”(())()”，在任何一个位置右括号的数量都不大于左括号的数量，所以是等效的。如果像这样”())()”第3个位置的是右括号，那么他前面只有一个左括号，而他和他前面的右括号有2个，那么无论如何都不能组合成有效的括号。搞懂了上面的原理，我们就以$n$等于$2$为例来画个图看一下

Java 代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(res, n, n, "");
        return res;
    }

    private void dfs(List<String> res, int left, int right, String curStr) {
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        // 左括号只有剩余的时候才可以选，如果左括号的数量已经选完了，是不能再选左括号了 
        // 如果选完了左括号我们还可以选择右括号
        if (left < 0) return;

        // 如果右括号剩余数量小于左括号剩余数量，说明之前选择的无效
        if (right < left) return;

        // 选择左括号
        dfs(res, left - 1, right, curStr + "(");

        // 选择右括号
        dfs(res, left, right - 1, curStr + ")");
    }
}