回溯法就是学不会2 —— 括号生成问题
题目描述： 给定括号数量， 判断其能生成的合法括号组合
示例：
括号数量 ： n = 2
输出结果： [(()), ()()]
为什么可以用回溯法：
本题解空间可以用树来表示， 在所有解的基础上去掉不合法结果（即剪枝），因此可以用回溯法解决
以 n = 2 为例， 本题的解空间树如下图所示
得到所有解：
输出结果为： [((((, (((), (()(, (()), ()((, ()(), ())(, ())), )(((, )((), )()(, )()), ))((, ))(), )))(, ))))]
// n为括号数量， path为临时字符串， result存储结果
public void dfs(int n, String path, List<String> result){
// 字符串长度为2倍的n时，结束
if(path.length() == 2*n){
result.add(path);
return;
}
// 加入左括号
dfs(n, path + "(", result);
// 加入右括号
dfs(n, path + ")", result);
}
剪枝：
方法： 引入开闭括号数量指针，open / close
- open或close数量大于 n, 剪枝——不合法，开闭括号数量超过最大数量
- close 数量大于 open , 剪枝 —— 不合法，有闭括号到开括号之前
加入剪枝函数后最终代码：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
dfs(n, "" , list, 0, 0);
return list;
}
// open,close分别表示开闭括号数量指针
public void dfs(int n, String path, List<String> result, int open, int close){
// 剪枝判断语句
if(open > n || close > open){
return;
}
if(path.length() == 2*n){
result.add(path);
return;
}
dfs(n, path + "(" , result, open+1, close);
dfs(n, path + ")", result, open, close+1);
}
}
最后感谢老师提供的思路，谢谢您！！！