22. 括号生成

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

示例 1：

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

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

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

括号生成，递归版本，动态规划的是在是看不太懂，其实思路非常简单，只要明白一些机制即可，当左右括号相等的时候，此时只能添加左括号，如果添加右括号就不匹配了，当左小于右的时候，添加左右都行，但是要确保左括号大于 0，首先递归入口：

getParenthesis("", n, n);

意思是，此时，左括号有 n 个，右括号有 n 个，并且字符串当前是 “” ，每次使用左括号，让左括号减一，都减到 0 的时候，return 即可

class Solution {
    List<String> list;
    public List<String> generateParenthesis(int n) {
        this.list = new ArrayList<>();
        getParenthesis("", n, n);
        return list;
    }
    public void getParenthesis(String s, int left, int right) {
        if (left == 0 && right == 0) {
            list.add(s);
            return ;
        }
        if (left == right) {
            getParenthesis(s + "(", left - 1, right);
        } else if (left < right){
            if (left > 0) {
                getParenthesis(s + "(", left - 1, right);
            }
            getParenthesis(s + ")", left, right - 1);
        }
    }
}