Question
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
TODO
Code
class Solution {
public List<String> generateParenthesis(int n) {
int l = n;
int r = n;
List<String> results = new ArrayList();
StringBuilder sb = new StringBuilder();
collect(results, l, r, sb);
return results;
}
private void collect(List<String> results, int l, int r, StringBuilder sb) {
if(r==0) {
results.add(sb.toString());
return;
}
if(l>0) {
sb.append("(");
collect(results, l-1, r, sb);
sb.deleteCharAt(sb.length()-1);
}
if(l<r) {
sb.append(")");
collect(results, l, r-1, sb);
sb.deleteCharAt(sb.length()-1);
}
}
}
Performance
TODO