Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
这题和二叉树其实挺像的,因为在每一个位置都只有两种可能 "(" 和 ")".
class Solution {
public static List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if (n == 0) {
return res;
}
helper(res, "", n, n);
return res;
}
public static void helper(List<String> res, String s, int left, int right) {
if (left > right) {
return;
}
if (left == 0 && right == 0) {
res.add(s);
return;
}
if (left > 0) {
helper(res, s + '(', left - 1, right);
}
if (right > 0) {
helper(res, s + ')', left, right - 1);
}
}
}