/**
1. 每次加状态的时候要符合括号规律, left > right 才能加右括号, left >= right 能加左括号
2. 状态定义: 每个位置的字符是'(' 还是 ')', 并维护左右括号的分别个数
状态计算: 下一个位置是 '(' 还是 ')', 总数有限
状态判断: 所有位置的填满了
*/
class Solution {
public List<String> generateParenthesis(int n) {
List<String> results = new ArrayList<>();
dfs(results, new StringBuilder(), 0, 0, n);
return results;
}
void dfs(List<String> results, StringBuilder buffer, int left, int right, int n) {
if (left == n && right == n) {
results.add(buffer.toString());
return;
}
if (left >= right && left < n) {
buffer.append('(');
dfs(results, buffer, left+1, right, n);
buffer.setLength(buffer.length()-1);
}
if (left > right && right < n) {
buffer.append(')');
dfs(results, buffer, left, right+1, n);
buffer.setLength(buffer.length()-1);
}
}
}
version at: 2020-3-25
/**
1. 深搜遍历所有可能的情况
1.1 搜索顺序: 每次尝试放入 (或) 当缓存长度为2n时输出
1.2 搜索状态: depth | set, buffer
1.3 剪枝: ~
1.4 复杂度 O(n ^ 2n)
2. 卡特兰数:
2.1 ( 最多n个
2.2 ) 最多( 个
2.3 先处理(, 后处理), 保证顺序合法
2.4 O(Combo(2n, n))
*/
class Solution {
public List<String> generateParenthesis(int n) {
return Catalan(n);
// return search(n);
}
List<String> Catalan(int n){
StringBuilder buffer = new StringBuilder();
List<String> result = new ArrayList<>();
gen(0, 0, n, result, buffer);
return result;
}
void gen(int l, int r, int n, List<String> res, StringBuilder buffer){
if (l == n && r == n){
res.add(buffer.toString());
return;
}
if (l < n){
buffer.append('(');
gen(l + 1, r, n, res, buffer);
if (buffer.length() > 0) buffer.setLength(buffer.length() - 1);
}
if (r < l){
buffer.append(')');
gen(l, r + 1, n, res, buffer);
if (buffer.length() > 0) buffer.setLength(buffer.length() - 1);
}
}
List<String> search(int n){
Set<String> set = new HashSet<>();
StringBuilder buffer = new StringBuilder();
dfs(2*n ,set, buffer);
List<String> result = new ArrayList<>();
for (String s : set)
result.add(s);
return result;
}
void dfs(int maxDepth, Set<String> set, StringBuilder buffer){
if (buffer.length() == maxDepth){
String candidate = buffer.toString();
if (check(candidate)) set.add(candidate);
return ;
}
buffer.append('(');
dfs(maxDepth, set, buffer);
if (buffer.length() > 0) buffer.setLength(buffer.length()-1);
buffer.append(')');
dfs(maxDepth, set, buffer);
if (buffer.length() > 0) buffer.setLength(buffer.length()-1);
}
boolean check(String s){
int stack = 0;
for (int i = 0 ; i < s.length(); i++){
if (s.charAt(i) == '('){
stack++;
} else if (stack <= 0) {
return false;
} else {
stack--;
}
}
return stack == 0;
}
}