Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[  "((()))",  "(()())",  "(())()",  "()(())",  "()()()"] 根据题目要求计算出所有可能性，我们使用回溯来处理，首先确定几个问题 1.必须先有左括号才能有右括号，不然序列不合法 2.左括号的个数必须小于给出的个数n 基于上面的条件，我们设计回溯的时候需要先放左括号，在有左括号的基础上才能有右括号，所以我们设置2个left和right来计算左右括号的个数 left
      

class Solution {    public List
       
         generateParenthesis(int n) {        List
        
          ans = new ArrayList();        backtrack(ans, "", 0, 0, n);        return ans;    }    public void backtrack(List
         
           ans, String cur, int open, int close, int max){        if (cur.length() == max * 2) {            ans.add(cur);            return;        }        if (open < max)            backtrack(ans, cur+"(", open+1, close, max);        if (close < open)            backtrack(ans, cur+")", open, close+1, max);    }}
         
        
       

 回溯就类似往栈里放东西，先进后出，所以所有可能性的个数就是一个卡特兰数，时间复杂度也就是这个卡特兰数