括号生成 （有效括号）

题目

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

解题思路

1. 先用全排列思想写出全部结果
2. 根据有效括号规则优化逻辑
   1. 左右括号数量必须相等
   2. 加右括号前左括号数量必须大于0

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

    public void generate (List<String> list,int left,int right,int n,String curStr){
        if (left + right == n*2){ //如果符合结果，那么加入数组
            list.add(curStr);
            return;
        }
        if(left < right){//如果做括号数量小于右括号 那么其余的都不符合结果
            return;
        }
        if (left < n){//左括号不可大于总括号数量
            generate (list,left+1,right,n,curStr+"(");
        }
        if (right < n){//右括号不可大于总括号数量
            generate (list,left,right+1,n,curStr+")");
        }
    }
}