【LeetCode】 22. 生成括号 回溯 JAVA
程序员文章站
2024-01-11 17:17:52
...
题目 |
题目传送门:传送门(点击此处)
题解 |
其实这道题目还是有难度的,如果没有放在回溯模块儿下,很难想到使用回溯的解决方案,也许是我太菜了哈哈哈
思路
- 括号是一对一对生成的,所以,必须先有
(
,再有)
。 - 每次递归,只需要有
(
和)
的数量,再有当前拼接成的字符串,就可以进行递归,获得结果。 - 递归就分为四种情况,
(
和)
都有可能有和没有,所以根据这四种情况进行判断就可以了
代码
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
if (n < 0) return res;
generate(n, 0, "");
return res;
}
// lLeft: 左括号剩余量
// rRight: 右括号剩余量
// preStr: 上一次generate的括号字符串
private void generate(int lLeft, int rLeft, String preStr) {
if (lLeft == 0 && rLeft == 0) {
res.add(preStr);
return;
} else if (lLeft == 0 && rLeft > 0) {
String str = preStr + ")";
int l = lLeft;
int r = rLeft - 1;
generate(l, r, str);
} else if (lLeft > 0 && rLeft > 0) {
String str1 = preStr + "(";
int l = lLeft - 1;
int r = rLeft + 1;
generate(l, r, str1);
String str2 = preStr + ")";
l = lLeft;
r = rLeft - 1;
generate(l, r, str2);
} else if (lLeft > 0 && rLeft == 0) {
String str = preStr + "(";
int l = lLeft - 1;
int r = rLeft + 1;
generate(l, r, str);
}
return;
}
}