题目链接：https://leetcode-cn.com/problems/generate-parentheses/

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

示例：

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

网上这道题的解法很多：动态规划，回溯算法等等

由于目前我还没有搞明白动态规划，所以就先说另一种方法……

我在这里要分享的是 ：递归+剪枝

方法1：递归

递归搜索出所有的可能结果，之后再判断括号是否合法，最后找出所有可能的结果。

这种方法的时间复杂度是O(2n)2的n次方，虽然能解决问题，但是复杂度还是太高了，所以还有优化的空间。

方法2：递归+剪枝

在递归的过程中，我们可以加入一些限制条件，在某些情况下不再递归下去。 比如：

1. 第一个就是右括号；
2. 拼接的括号里右括号多于左括号；
3. 左右括号数量多于给定的数量n。

接下来看代码：

class Solution {
    public List<String> generateParenthesis(int n) {
       List<String> list = new ArrayList<>();
       generate("", list, n, n);
       return list;
    }
    // 辅助函数 left，right：左右括号可使用的数量
    public void generate(String str, List<String> result, int left, int right)  {
        // 如果左右括号都用完了就结束递归
        if (left==0&&right==0) {
            result.add(str);
            return;
        }
          // 只要左括号没用完，都可以加
        if (left>0) {
            generate(str+"(", result, left-1, right);
        }
        // 只要右括号可用数量比左括号多就可以加
        if (right>left) {
            generate(str+")", result, left, right-1);
        }
    }
}