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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
public class Solution {
private List<String> list = new ArrayList<String>();
public List<String> generateParenthesis(int n) {
run("", n, 0);
return list;
}
// l 为剩余左括号数，r为剩余未匹配的右括号数目
public void run(String str, int l, int r) {
if (l == 0 && r == 0) {
list.add(str);
return; //跳出run方法
}
if (l > 0) {
String s = str + "(";
run(s, l-1, r+1);
}
if (r > 0) {
String s = str + ")";
run(s, l, r-1);
}
}
}
程序结果：