数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
思路：dfs 回溯
1. 产生有效解的情况是left和right均等于n
2. 如果left < right, 说明当前字符串中右括号数多于左括号数，这是不不符合要求的，可以提前终止
3. 如果left < n, 说明还有剩余的左括号没用完，可以继续递归左括号
4. 如果right < n, 说明还有剩余的右括号没用完，还可以继续递归右括号
做加法：
1 class Solution { 2 public List generateParenthesis(int n) { 3 // dfs回溯 4 List res = new ArrayList (); 5 if(n == 0) 6 return res; 7 dfs(res, 0, 0,n, ""); 8 return res; 9 }10 11 public void dfs(List res, int left, int right, int n, String curStr){12 // 如果left和right都等于n了，说明已经生产了一个解13 if(left == n && right == n){14 res.add(curStr);15 return;16 }17 // 剪枝，如果left < right, 说明当前字符串中右括号数多于左括号数，这是不不符合要求的，可以提前终止18 if(left < right){19 return;20 }21 22 // 如果左括号数小于n说明还可以继续递归左括号23 if(left < n){24 dfs(res, left + 1, right, n, curStr + "(");25 }26 27 // 如果右括号小于n，说明还可以继续递归右括号28 if(right < n){29 dfs(res, left, right + 1, n, curStr + ")");30 }31 }32 } 复杂度分析
上面的程序是对left 和 right 做加法，这里写个做减法的程序：
1 class Solution { 2 public List generateParenthesis(int n) { 3 // dfs回溯 4 5 List res = new ArrayList (); 6 if(n == 0) 7 return res; 8 dfs(res, n, n,n, ""); 9 return res;10 }11 12 public void dfs(List res, int left, int right, int n, String curStr){13 // 如果left和right都等于n了，说明已经生产了一个解14 if(left == 0 && right == 0){15 res.add(curStr);16 return;17 }18 // 剪枝，如果left > right, 说明当前字符串中右括号数多于左括号数，这是不不符合要求的，可以提前终止19 if(left > right){20 return;21 }22 23 // 如果左括号数大于0，说明还可以继续递归左括号24 if(left > 0){25 dfs(res, left - 1, right, n, curStr + "(");26 }27 28 // 如果右括号大于0，说明还可以继续递归右括号29 if(right > 0){30 dfs(res, left, right - 1, n, curStr + ")");31 }32 }33 } 使用标准的回溯，
上面两个程序其实是利用了String的不可变性，每个对 curStr 加上左右括号后其实对当前层次的curStr是没有影响的，相当于curStr自动回溯了，这里用StringBuilder代替String,标准的写一遍回溯，加深回溯的印象
1 class Solution { 2 public List generateParenthesis(int n) { 3 // dfs回溯 4 5 List res = new ArrayList (); 6 if(n == 0) 7 return res; 8 StringBuilder curStr = new StringBuilder(); 9 dfs(res, n, n,n, curStr);10 return res;11 }12 13 public void dfs(List res, int left, int right, int n, StringBuilder curStr){14 // 如果left和right都等于n了，说明已经生产了一个解15 if(left == 0 && right == 0){16 res.add(curStr.toString());17 return;18 }19 // 剪枝，如果left > right, 说明当前字符串中右括号数多于左括号数，这是不不符合要求的，可以提前终止20 if(left > right){21 return;22 }23 24 // 如果左括号数大于0，说明还可以继续递归左括号25 if(left > 0){26 curStr.append("(");27 dfs(res, left - 1, right, n, curStr);28 curStr.deleteCharAt(curStr.length() - 1); // 回溯到添加前的转态29 }30 31 // 如果右括号大于0，说明还可以继续递归右括号32 if(right > 0){33 curStr.append(")");34 dfs(res, left, right - 1, n, curStr);35 curStr.deleteCharAt(curStr.length() - 1); // 回溯到添加前的转态36 }37 }38 }