生成括号
给定 n 对括号,请写一个函数以将其生成新的括号组合,并返回所有组合结果。
样例
给定 n = 3
, 可生成的组合如下:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题
采用递归树的思想
left: 左括号的数量
right:右括号数量
n:括号的对数
当left == n:表示左括号已经到达最大值了,只能添加右括号
当left >= right: 表示左括号数量 小于 右括号数量,可以添加左括号 也可以添加右括号
当left < right or left >n or right >n : 非法操作
public class Solution {
/**
* @param n n pairs
* @return All combinations of well-formed parentheses
*/
public ArrayList<String> generateParenthesis(int n) {
// Write your code here
ArrayList<String> result = new ArrayList<String>();
if(n<=0)
return result;
int left = 0,right=0;
String str="";
generateParenthesis(n,left,right,str,result);
return result;
}
public void generateParenthesis(int n,int left,int right,String str ,ArrayList<String> result){
if(left >n || right >n || left < right)
return;
if(left == n){
for(int i=0;i< n- right;i++)
str+=")";
result.add(str);
return;
} // left>=right
generateParenthesis(n, left+1, right,str+"(",result);
generateParenthesis(n, left, right+1,str+")",result); }
}
下面的程序参考上面博客链接中,感觉判断添加是不是少了。
public class Solution {
/**
* @param n n pairs
* @return All combinations of well-formed parentheses
*/
public ArrayList<String> generateParenthesis(int n) {
// Write your code here
ArrayList<String> result = new ArrayList<String>();
if(n<=0)
return result;
int left = 0,right=0;
String str="";
generateParenthesis(n,left,right,str,result);
return result;
}
public void generateParenthesis(int n,int left,int right,String str ,ArrayList<String> result){
if(left == n){
for(int i=0;i< n- right;i++)
str+=")";
result.add(str);
return;
}
generateParenthesis(n, left+1, right,str+"(",result);
if(left>right){
generateParenthesis(n, left, right+1,str+")",result);
}
}
}