Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Solution:
关键的点在于任意时刻,左边的括号数目要大于等于右边的括号数目。最开始的一个一定是左括号,总共字符串的字符数目为2n,第一个确定,所以我们需要确定剩下2n-1个字符的位置。
n为还需要添加的字符数目
num为字符串中左括号比右括号多的个数
class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> list = new ArrayList<String>();
String s = new String("(");
generate(list, s, 2*n-1, 1);
return list;
}
//s为没有完成的字符串
//n为还需要添加的字符数目
//num为字符串中左括号比右括号多的个数
public void generate(ArrayList<String> list, String s, int n, int num) {
//递归出口
if(n == 0) { //说明全部添加完毕
list.add(s);
return;
}
if(n < 0) { //左括号比右括号少,非法
return;
}
if(num == 0) { //字符串左括号和右括号相等,那么下一个只能为左括号
//s = s + "(";
generate(list, s + "(", n-1, num+1);
}else if(num >= 1 && n > num) { //{
generate(list, s + "(", n-1, num+1);
generate(list, s + ")", n-1, num-1);
}else { //n=num,说明除了num个左括号所需要匹配的右括号,
generate(list, s + ")", n-1, num-1);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)