数字?n?代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且?有效的?括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8?
bool isRight(vector<char> &str)
{
?? ?stack<char>stkRight;
?? ?for (int i = 0; i<str.size(); i++)
?? ?{
?? ??? ?if (stkRight.size() == 0 && str[i] == ')')
?? ??? ?{
?? ??? ??? ?return false;
?? ??? ?}
?? ??? ?if (str[i] == ')' && stkRight.size()>0)
?? ??? ?{
?? ??? ??? ?stkRight.pop();
?? ??? ??? ?continue;
?? ??? ?}
?? ??? ?if (str[i] == '(')
?? ??? ?{
?? ??? ??? ?stkRight.push(str[i]);
?? ??? ??? ?continue;
?? ??? ?}
?? ?}
?? ?if (stkRight.size() == 0)
?? ?{
?? ??? ?return true;
?? ?}
?? ?return false;
}
vector<vector<char>>ret;
vector<char>tarVec = { '(',')' };
void dfs(vector<char>&vec, int cur, int n)
{
?? ?if (cur == 2 * n )
?? ?{
?? ??? ?ret.push_back(vec);
?? ??? ?return;
?? ?}
?? ?for (int i = 0; i<tarVec.size(); i++)
?? ?{
?? ??? ?vec.push_back(tarVec[i]);
?? ??? ?dfs(vec, cur + 1, n);
?? ??? ?vec.pop_back();
?? ?}
}
vector<string> generateParenthesis(int n) {
?? ?vector<string> ret2;
?? ?vector<char>vec;
?? ?dfs(vec, 0, n);
?? ?for (int i = 0; i<ret.size(); i++)
?? ?{
?? ??? ?if (isRight(ret[i]))
?? ??? ?{
?? ??? ??? ?string str = "";
?? ??? ??? ?for (int j = 0; j<ret[i].size(); j++)
?? ??? ??? ?{
?? ??? ??? ??? ?str += ret[i][j];
?? ??? ??? ?}
?? ??? ??? ?ret2.push_back(str);
?? ??? ?}
?? ?}
?? ?return ret2;
}
?