Description
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
DFS
class Solution {
public List<String> generateParenthesis(int n) {
List<String> parentheses = new ArrayList();
if (n < 1) return parentheses;
StringBuilder sb = new StringBuilder();
generateParenthesis(n, n, sb, parentheses);
return parentheses;
}
public void generateParenthesis(int left, int right, StringBuilder sb
, List<String> parentheses) {
if (left < 0 || right < 0 || left > right) {
return;
}
if (left == 0 && right == 0) {
parentheses.add(sb.toString());
return;
}
sb.append('(');
generateParenthesis(left - 1, right, sb, parentheses);
sb.setCharAt(sb.length() - 1, ')');
generateParenthesis(left, right - 1, sb, parentheses);
sb.deleteCharAt(sb.length() - 1);
}
}
