leetcode 算法 22. 括号生成
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result,new StringBuilder(),0,0,n);
return result;
}
public void backtrack(List<String> result,StringBuilder builder,int left,int right,int limit){
if(left == limit && right == limit){
result.add(builder.toString());
return;
}
// 有效闭合 ( 使用的不能少于 )
if(right > left){
return;
}
if(left < limit){
builder.append("(");
backtrack(result,builder,left+1,right,limit);
builder.deleteCharAt(builder.length()-1);
}
if(right < limit){
builder.append(")");
backtrack(result,builder,left,right+1,limit);
builder.deleteCharAt(builder.length()-1);
}
}
}
思路：
1、枚举所有可能，回溯法进行深度优先遍历
2、有效组合需要对（ 和 ）的使用顺序作限制，顺序遍历 left 始终 >= right
