给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
代码语言：javascript复制[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]思路：只要有左括号就可以添加
代码语言：javascript复制class Solution {
List<String> list = new ArrayList();
public List<String> generateParenthesis(int n) {
int left = n;
int right = n;
helper(left,right,"");
return list;
}
public void helper(int left,int right,String str){
if(left==0&&right==0){
list.add(str);
return;
}
if(left>0){
// str ="(";
// --left;
helper(left-1,right,str "(");
}
if(right>0&&right>left){
// str =")";
// --right;
helper(left,right-1,str ")");
}
}
}思路2: 这其实是可以通过回溯来进行解决的问题，也就是dfs
代码语言：javascript复制class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> res = new ArrayList();
if(n==0){
return res;
}
int right = n;
int left = n;
LinkedList<String> stack = new LinkedList();
addParenthesis(right,left,stack,res);
return res;
}
String getRes(LinkedList<String> stack){
String res = "";
for(String s : stack){
res = res s;
}
return res;
}
public void addParenthesis(int right,int left,LinkedList<String> stack,ArrayList<String> res){
if(right==0&&left==0){
res.add(getRes(stack));
return;
}
if(left>right){
return;
}
if(left<0||right<0){
return;
}
stack.addLast("(");
// left--;
addParenthesis(right,left-1,stack,res);
stack.removeLast();
stack.addLast(")");
// right--;
addParenthesis(right-1,left,stack,res);
stack.removeLast();
}
}
