原题，题目描述：
分类标签也是回溯，其实我做了这么多天的回溯题后，我发现回溯其实和动态规划其实也蛮像的（其实不如说递归和动态规划的思想本来就挺像，至少我是这么认为的）。这道题题目很简单，就是给定一个数字，我们需要使用这个长度来生成一个括号序列，并且必须是符合条件的括号序列，具体看原题的描述。
看到这题的时候还是思考了一下的。然后我产生的第一思路如下：
思路一
我们需要有效的括号序列，那我们可以以一个完整的括号为单位，在序列里面移动，如下：
例如已经回溯到了当前函数，传回来的括号序列是 （） ，我们可以以 （） 为单位移动：(()) ()()
代码一
这样有一个坏处，那就是会产生一些重复的序列，不过我们使用set去重即可，我们这里直接给出代码：
class Solution {
public List<String> generateParenthesis(int n) {
if (n == 1) {
ArrayList<String> res = new ArrayList<>();
res.add("()");
return res;
}
List<String> list = generateParenthesis(n - 1);
HashSet<String> set = new HashSet<>();
for (String s : list) {
int length = s.length();
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c=='('||c==')'){
sb.insert(i+1,"()");
set.add(sb.toString());
sb.delete(i+1,i+3);
}
}
}
return set.stream().toList();
}
}
提交后跑了5毫秒，只打败了百分之10左右。这个成绩当然是不满意的，于是我就在寻找优化点，我尝试了很多优化，但是都不太能改善这个成绩。于是我去看了官解，官解给出了三种解答，一种是暴力，这里我们不管，一种是我上述的解法一，我们学习最后的一种。
思路二
括号都是成对存在，我们给出括号多少n，就可以确认左右括号的数量，那我们只要在满足这个数量的前提下，再满足有效即可。那我们可以去一个个放置左右括号。首先左括号的放置是无要求的，只要不超过n即可，右括号有要求，思考一下：首先一个左括号都没放的时候，当然是不能放置右括号的。然后就是当前序列里，右括号的数量一定得小于左括号数量（在当前右括号放下前），为什么，思考一下，如果右括号数量超过的左括号，那左边就是没有闭合的，这个原理比较显然。我们将括号放置完毕后，也就是左右括号的剩余数量都等于0的时候，直接将序列添加进集合即可。
代码二
我们看代码：
class Solution {
private ArrayList<String> generateParenthesisRes = new ArrayList<>();
public List<String> generateParenthesis(int n) {
generateParenthesis2(n, n, new StringBuilder());
return generateParenthesisRes;
}
public void generateParenthesis2(int left, int right, StringBuilder sb) {
if (left == 0 && right == 0) {
generateParenthesisRes.add(sb.toString());
}
if (left > 0) {
sb.append('(');
generateParenthesis2(left - 1, right, sb);
sb.deleteCharAt(sb.length() - 1);
}
if (left < right) {
sb.append(')');
generateParenthesis2(left, right-1, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}
这份代码的速度和空间都很优秀。提交后接近双百。这道题的时空复杂度计算比较复杂，所以这里不做分析，想了解可以去看官方的分析。