題目
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
答案
The idea is to prevent your backtracking algorithm from generating any invalid strings on the fly.
So then, when your algorithm generates up to n * 2 chars, it has to be valid.
···
class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
if(n == 0) return list;
recur(n, 0, new StringBuilder(), list, 0, 0);
return list;
}
/*
Rules
cannot have more than n
*/
private void recur(int n, int i, StringBuilder curr, List<String> list, int numl, int numr) {
if(i == n * 2) {
list.add(curr.toString());
return;
}
// let ith char be left paren
if(numl < n) {
recur(n, i + 1, curr.append('('), list, numl + 1, numr);
curr.deleteCharAt(curr.length() - 1);
}
// let ith char be right paren
if(numr < numl) {
recur(n, i + 1, curr.append(')'), list, numl, numr + 1);
curr.deleteCharAt(curr.length() - 1);
}
}
}
···
