LeetCode 22 Generate Parentheses
概述
https://leetcode.com/problems/generate-parentheses/
如何保证括号是合法的呢？
回溯法（利用双栈保证合法）
我这里是用两个 stack：
class Solution {
public:
int n;
vector<string> ans;
vector<string> generateParenthesis(int n) {
this->n = n;
vector<char> sa;
vector<char> sb;
backtrack(sa, sb, 0);
return ans;
}
void backtrack(vector<char>& sa, vector<char>& sb, int i) {
if (i == n && sb.empty()) {
string t(sa.begin(), sa.end());
ans.push_back(t);
return;
}
if (!sb.empty()) {
sb.pop_back();
sa.push_back(')');
backtrack(sa, sb, i);
sa.pop_back();
sb.push_back(')');
}
if (i < n) {
sa.push_back('(');
sb.push_back(')');
backtrack(sa, sb, i + 1);
sb.pop_back();
sa.pop_back();
}
}
};
由于回溯法的性质（执行完选择后回溯到执行前的状态），后面的那两个 if 的顺序无所谓。
回溯法（依靠剩余的左右括号个数判断是否合法）
如果剩余的右括号个数小于左括号个数，说明不合法。
class Solution {
public:
vector<string> ans;
vector<string> generateParenthesis(int n) {
vector<char> s;
backtrack(n, n, s);
return ans;
}
void backtrack(int l, int r, vector<char>& s) {
if (l == 0 && r == 0) {
string t(s.begin(), s.end());
ans.push_back(t);
return;
}
if (l > r) return;
if (l > 0) {
s.push_back('(');
backtrack(l-1, r, s);
s.pop_back();
}
if (r > 0) {
s.push_back(')');
backtrack(l, r-1, s);
s.pop_back();
}
}
};
关于时间复杂度：
对于 backtrack 函数，状态有三个，分别是 left, right, track，这三个变量的所有组合个数就是 backtrack 函数的状态个数（调用次数）。 left 和 right 的组合好办，他俩取值就是 0~n 嘛，组合起来也就 n^2 种而已；这个 track 的长度虽然取在 0~2n，但对于每一个长度，它还有指数级的括号组合，这个是不好算的。 说了这么多，就是想让大家知道这个算法的复杂度是指数级，而且不好算，这里就不具体展开了，是 4^n / sqrt(n)，有兴趣的读者可以搜索一下「卡特兰数」相关的知识了解一下这个复杂度是怎么算的。