括号生成

难度中等

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

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

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

Language: Java

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

    private void traverse(List<String> res,String single, int left, int right) {
        if (left == 0 && right == 0){
            res.add(single);
            return;
        }
            
        if (left > 0) {
            traverse(res, single+"(", left - 1 , right);
        }
        if (right > 0 && right > left) {
            traverse(res, single+")", left, right - 1);
        }
    }
}

思路：

想一想这种生成括号的规则，其实隐含了一条信息：那就是始终左括号的数量要大于或等于右括号的数量。也就是说，剩余的左括号的数量要始终小于等于右括号。左括号只要有，就可以打印；而只有当剩余的右括号数量比左括号大时，才能打印右括号。为了方便理解，我现在假设n = 2，那么根据刚才我说的隐含信息，逻辑应该是这样的：

肯定要先取一个左括号，此时左括号剩余的数量变为1，右括号剩余数量还是2
第二位取左括号也行，取右括号也行。如果取左括号，那么此时右括号剩余数量为2，左括号剩余数量为0，长成了这个样子”((“；如果取右括号，左右剩余数量都是1，长成这个样子”()”
第三位，如果剩余左括号没了，就只能跟进右括号了，连续两个，最终变成”(())”；而如果现在是”()”的，那么要先左后右，最终变成”()()”.

发现，每一步都有两种选择：左或者右，当然不一定都可行，如果可行，那么往后继续，不可行，终止。

这是什么，二叉树。对于n = 2的情况，他的二叉树应该是这样的：

这棵二叉树表达的东西其实跟我刚才说的是一样的，而我们所要的结果就是这棵二叉树遍历所有路径的结果。由此，不妨先来回忆一下之前“二叉树的所有路径”这道题目（详见：点击打开链接）可以仿照这个方法来解决我们当前的问题。所不同的是，这里我们没有一棵已经给出的二叉树，但是，此处，我们相当于知道了这棵二叉树的左右节点是否为空的条件（就是一开始的隐含信息，左括号要始终大于等于右括号，也就是说剩余的左括号要始终小于等于剩余的右括号），以及不为空时，节点的值（左括号为”(“，右括号为”)”）。

来源： <https://blog.csdn.net/guoziqing506/article/details/51198069 >