数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1
输出：["()"]提示：
1 <= n <= 8
解题思路：回溯 + 剪枝
这道题其实就是一个暴力搜索，我们在搜索之前还需要知道有效的括号组合的要求：
- 左括号数量 = 右括号数量 =
n。 - 在遍历途中，保证三个小要求：
- 左括号数量不超过
n。 - 右括号数量不超过
n。 - 左括号数量一定要大于等于右括号数量，才能保证右括号至少有一个左括号与之匹配。
- 左括号数量不超过
知道了有效的括号组合要求之后，就是开始构建一棵决策树，其实就是每次看选左括号还是右括号，然后选完之后再递归继续选，直到最后符合上述的要求为止，决策树如下图所示，以 n=2 为例：
所以为了达到剪枝的效果，我们需要有一个 left 和一个 right 变量，来记录当前左括号和右括号的数量，如果不符合上述的要求的话直接就剪枝了！
然后在递归的时候，如果选择的是左括号的话，则让 left+1，如果选择的是右括号的话则让 right+1 去递归，这里我们将这两个变量设为局部变量，这样子每一层的 left 和 right 就不会互相干扰，就不用在回溯的时候进行处理！
剩下的细节都是一样的，具体参考代码！
class Solution {
private:
vector<string> ret; // 存放结果集
string path; // 存放当前路径的字符串
public:
vector<string> generateParenthesis(int n) {
dfs(n, 0, 0);
return ret;
}
void dfs(int n, int left, int right)
{
// 递归函数出口
if(left > n || right > n || right > left)
return;
// 如果满足括号数量则添加结果集并且返回
if(left == n && right == n)
{
ret.push_back(path);
return;
}
string tmp = "()";
for(int i = 0; i < tmp.size(); ++i)
{
// 处理当前节点
path.push_back(tmp[i]);
// 递归后面的路径
if(tmp[i] == '(')
dfs(n, left + 1, right);
else
dfs(n, left, right + 1);
// 回溯处理
path.pop_back();
}
}
};