数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
思路一：回溯
class Solution {
public:
vector<string> generateParenthesis(int n) {
std::vector<std::string> res{};
std::string tmp{};
AddParenthesis(res, tmp, n, n);
return res;
}
void AddParenthesis(std::vector<std::string>& res, std::string& tmp, int l, int r) {
if (l > r || l < 0) return;
if (l == 0 && r == 0) {
res.push_back(tmp);
return;
}
tmp += '(';
AddParenthesis(res, tmp, l-1, r);
tmp.pop_back();
tmp += ')';
AddParenthesis(res, tmp, l, r-1);
tmp.pop_back();
}
};
思路二：动态规划
- 当我们要给出n个括号对组成的结果集 f(n)时，在这个结果中，所有字符串的第一个元素必然是 "("
- 那么必然有另一个与之匹配的右括号 ")"
- 那么还有 n-1 个括号对需要安放
- 这 n-1 个括号对中，可以有 j 个括号对位于上述这对括号的内部，那么剩余的 n-1-j 个括号对都在上述括号对右侧
- j的取值范围应该是 [0, n-1]
- 所以在计算f(n)时， 我们是需要知道 f(0), f(1), ... f(n-1)的结果的，因此需要用map保存dp过程中的每一个结果
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) return {};
if (n == 1) return { "()" };
vector<vector<string>> dp(n+1);
dp[0] = { "" };
dp[1] = { "()" };
for (int i = 2; i <= n; i++) {
for (int j = 0; j <i; j++) {
for (string p : dp[j])
for (string q : dp[i - j - 1]) {
string str = "(" + p + ")" + q;
dp[i].push_back(str);
}
}
}
return dp[n];
}
};