括号生成

题目链接：括号生成

题目描述：

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

示例：

输入：n = 3 输出：[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ] 代码：

class Solution{ int n; char[] cur = new char[n*2]; List<String> res = new ArrayList(); solve(cur,0,res,0,0); } public void solve(char[] cur,int pos,List<String> res,int left,int right){ if(pos == cur.length){ //if(isOk(cur)) res.add(new String(cur));剪枝前 res.add(new String(cur)); } if(left<(cur.length/2)){ //左括号数量一定小于N cur[pos]= '('; solve(cur,pos+1,res,left+1,right); } if(right<left){ //右括号数量一定小于左括号 cur[pos]= ')'; solve(cur,pos+1,res,left,right+1); } } //判断是否合法 public boolean isOK(char[] ch){ int cnt = 0; for(char c:ch){ if(c == '(') cnt++; else cnt--; } return cnt == 0; }