附上原題：
給定n個圓括號，要求生成所有的正確組合形式玻淑。何謂正確呀伙，就是說一對圓括號必須是兩兩配對。
記得有一道很經(jīng)典的題目剿另，數(shù)據(jù)結(jié)構(gòu)課程中關(guān)于棧的應(yīng)用常常會以這個為例，就是說給定幾對括號雨女，怎么判斷括號是正確配對的。如果能用到棧就很好辦了氛堕，對字符串進(jìn)行遍歷，碰到左括號入棧讼稚，碰到右括號出棧，當(dāng)所有的字符串遍歷完成后锐想，棧為空則正確配對，反之則不正確赠摇，我們的好朋友編譯器其實(shí)就是這么干的固逗。
那現(xiàn)在問題是不是也能用棧來保證括號配對的正確性呢藕帜？我們不妨來試一下。
- 首先我們定義一個棧S1洽故，并定義一個字符串變量STR。
- 第一次收津，棧為空，只能將左括號入棧撞秋，并且字符串后追加一個左括號。
- 接下來?xiàng)２粸榭瘴腔撸蔷陀袃煞N選擇串结，可以選擇繼續(xù)入棧，也可以選擇出棧肌割，又是一個DFS問題??。如果選擇出棧把敞，從S1中將最后一個元素彈出，并在STR上追加一個右括號奋早，這個不難理解。
- 最后如果字符串括號對數(shù)達(dá)到了n耽装，將結(jié)果保存。
這里注意一個邊界條件掉奄，每次入棧的時候，下次遞歸應(yīng)該將n - 1姓建，當(dāng)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 保存最終的結(jié)果，為了節(jié)省資源憨栽，可以聲明為引用變量
* s 算法用到的棧，不能將棧聲明為引用屑柔，否則在遞歸過程中會對上一層造成干擾
* str 保存每一種組合
* n 當(dāng)前可以繼續(xù)添加的括號對數(shù)
*/
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);
//棧返回后，要將數(shù)據(jù)還原饰序，切記！
str = str.substr(0, str.size() - 1);
s.pop();
popParenthesis(s, str);
dfs(s, result, str, n);
}
} else { //此時求豫，括號對數(shù)達(dá)到n诉稍，將結(jié)果保存
result.push_back(str);
}
}
void pushParenthesis(stack<char> &s, string &str) {
s.push('(');
str += '(';
}
void popParenthesis(stack<char> &s, string &str) {
s.pop();
str += ')';
}
};
