附上原题：
给定n个圆括号，要求生成所有的正确组合形式。何谓正确，就是说一对圆括号必须是两两配对。
记得有一道很经典的题目，数据结构课程中关于栈的应用常常会以这个为例，就是说给定几对括号，怎么判断括号是正确配对的。如果能用到栈就很好办了，对字符串进行遍历，碰到左括号入栈，碰到右括号出栈，当所有的字符串遍历完成后，栈为空则正确配对，反之则不正确，我们的好朋友编译器其实就是这么干的。
那现在问题是不是也能用栈来保证括号配对的正确性呢？我们不妨来试一下。
- 首先我们定义一个栈S1，并定义一个字符串变量STR。
- 第一次，栈为空，只能将左括号入栈，并且字符串后追加一个左括号。
- 接下来栈不为空，那就有两种选择，可以选择继续入栈，也可以选择出栈，又是一个DFS问题😂。如果选择出栈，从S1中将最后一个元素弹出，并在STR上追加一个右括号，这个不难理解。
- 最后如果字符串括号对数达到了n，将结果保存。
这里注意一个边界条件，每次入栈的时候，下次递归应该将n - 1，当n = 0的时候，只能选择出栈。
代码如下：
class Solution {
public:
vector<string> generateParenthesis(int n) {
stack<char> s;
vector<string> result;
string str;
dfs(s, result, str, n);
return result;
}
private:
/*
* result 保存最终的结果，为了节省资源，可以声明为引用变量
* s 算法用到的栈，不能将栈声明为引用，否则在递归过程中会对上一层造成干扰
* str 保存每一种组合
* n 当前可以继续添加的括号对数
*/
void dfs(stack<char> s, vector<string> &result, string str, int n) {
if (!s.empty() || n != 0) {
if (s.empty()) { //栈为空，只能入栈
pushParenthesis(s, str);
dfs(s, result, str, n - 1);
} else if (n == 0) { //没有可添加的括号，只能出栈
popParenthesis(s, str);
dfs(s, result, str, n);
} else {
//否则，可以选择入栈或出栈
pushParenthesis(s, str);
dfs(s, result, str, n - 1);
//栈返回后，要将数据还原，切记！
str = str.substr(0, str.size() - 1);
s.pop();
popParenthesis(s, str);
dfs(s, result, str, n);
}
} else { //此时，括号对数达到n，将结果保存
result.push_back(str);
}
}
void pushParenthesis(stack<char> &s, string &str) {
s.push('(');
str += '(';
}
void popParenthesis(stack<char> &s, string &str) {
s.pop();
str += ')';
}
};
