题目不难，熟悉回溯可以无脑写出代码，但是要优化时间复杂度，需要进一步的工作：
无脑回溯 百分之五
class Solution {private List<String> rs;private char[] c=new char[]{'(',')'};private boolean valid(StringBuilder sb){ArrayDeque<Character> stack=new ArrayDeque<>();for(char cc:sb.toString().toCharArray()){if(cc=='('){stack.push(cc);}else{if(stack.isEmpty()){return false;}else{stack.pop();}}}return stack.isEmpty();}private void helper(int n,int cur,StringBuilder sb){if(cur==n){if(valid(sb)){rs.add(sb.toString());}return;}for(char cc:c){sb.append(cc);helper(n,cur+1,sb);sb.deleteCharAt(sb.length()-1);}}public List<String> generateParenthesis(int n) {rs=new ArrayList<>();helper(2*n,0,new StringBuilder());return rs;}
}```
稍微剪枝，如果左括号数量和右括号不等，那么直接false，不需要栈来判断 百分之十二
class Solution {private List<String> rs;private char[] c=new char[]{'(',')'};private int left,right;private boolean valid(StringBuilder sb){if(left!=right){return false;}ArrayDeque<Character> stack=new ArrayDeque<>();for(char cc:sb.toString().toCharArray()){if(cc=='('){stack.push(cc);}else{if(stack.isEmpty()){return false;}else{stack.pop();}}}return stack.isEmpty();}private void helper(int n,int cur,StringBuilder sb){if(cur==n){if(valid(sb)){rs.add(sb.toString());}return;}for(char cc:c){sb.append(cc);if(cc=='('){left++;}else{right++;}helper(n,cur+1,sb);sb.deleteCharAt(sb.length()-1);if(cc=='('){left--;}else{right--;}}}public List<String> generateParenthesis(int n) {rs=new ArrayList<>();helper(2*n,0,new StringBuilder());return rs;}
}```
再次剪枝，如果left<right(因为任何位置，左括号都不能少于右括号，因为如果该位置之前右括号更多，那么一定无法配对），或者left>n（左括号数不能大于括号对数），都应该立刻返回
class Solution {private List<String> rs;private char[] c=new char[]{'(',')'};private int left,right;private boolean valid(StringBuilder sb){if(left!=right){return false;}ArrayDeque<Character> stack=new ArrayDeque<>();for(char cc:sb.toString().toCharArray()){if(cc=='('){stack.push(cc);}else{if(stack.isEmpty()){return false;}else{stack.pop();}}}return stack.isEmpty();}private void helper(int n,int cur,StringBuilder sb){if(left<right||left>n/2){return;}if(cur==n){if(valid(sb)){rs.add(sb.toString());}return;}for(char cc:c){sb.append(cc);if(cc=='('){left++;}else{right++;}helper(n,cur+1,sb);sb.deleteCharAt(sb.length()-1);if(cc=='('){left--;}else{right--;}}}public List<String> generateParenthesis(int n) {rs=new ArrayList<>();helper(2*n,0,new StringBuilder());return rs;}
}```发现完全不需要用栈来检测括号，因为只要符合之前提到的两个约束，那么总是valid 1ms
class Solution {private List<String> rs;private char[] c=new char[]{'(',')'};private int left,right;private void helper(int n,int cur,StringBuilder sb){if(left<right||left>n/2){return;}if(cur==n){if(left==right){rs.add(sb.toString());}return;}for(char cc:c){sb.append(cc);if(cc=='('){left++;}else{right++;}helper(n,cur+1,sb);sb.deleteCharAt(sb.length()-1);if(cc=='('){left--;}else{right--;}}}public List<String> generateParenthesis(int n) {rs=new ArrayList<>();helper(2*n,0,new StringBuilder());return rs;}
}```