题解 | #括号生成#
括号生成
https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca
2022.0901算法第50题括号生成
这题刚开始想到使用全排列，然后通过判断得到的排列是否符合要求进行存储。
但是结果字符中的判断并不好进行，使用左右括号出现的数量作比较应该可以。
最主要的原因是超时，n对括号进行的全排列就是2n级别的，当n=8时时间就超了
之后看了解析发现这题使用的套路并没有那么明显
将n对括号分为左右两个，根据左括号和右括号的关系进行递归，没感觉有回溯
这个感觉好难想，想不明白怎样进行的了
vector<string> res;
void backtrack(int n,int left,int right,string &path){
//left==right==n，表示先判断left==right然后将结果与n做判断，这样是不对的
//left==n&&right==n才是正确的
//终止条件，左括号和右括号都等于n时，满足条件
if(left==n&&right==n){
res.push_back(path);
return ;
}
//当左括号小于n时，就可以选择左括号
if(left<n){
//这里的递归回溯逻辑没捋清楚，还需要再想想
path.push_back('(');
backtrack(n, left+1, right, path);
path.pop_back();
}
//当右括号小于n并且右括号数量小于左括号数量就可以选择右括号
if(right<n&&left>right){
path.push_back(')');
backtrack(n, left, right+1, path);
path.pop_back();
}
}
vector<string> generateParenthesis(int n) {
string path;
backtrack(n, 0, 0, path);
return res;
}
这个代码不再是for循环，而是if判断
这样产生的树，应该每个节点最多只有两个分支，应该是个二叉树
不清楚为什么
backtrack(n, left, right+1, path+')');这样也能过，这样感觉并没有进行回溯，path变量不会一直添加字符吗？
我理解的应该递归中全程使用的都是path变量
待续。。。
#算法题#待续。。。
