题目描述
blablabla
样例
blablabla
算法1
时间复杂度
直接生成合法的序列一定满足右括号的个数总是小于等于左括号的个数,是一个典型的卡特兰数问题,卡特兰数的时间复杂度是
Java 代码
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(0, 0, n, new StringBuilder());
return res;
}
private void dfs(int l, int r, int n, StringBuilder sb){
if(sb.length() == 2*n){
res.add(sb.toString());
return;
}
if(l < n){
sb.append('(');
dfs(l+1,r,n,sb);
sb.deleteCharAt(sb.length()-1);
}
if(r < l){
sb.append(')');
dfs(l,r+1,n,sb);
sb.deleteCharAt(sb.length()-1);
}
}
}