版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請注明出處。
個人博客地址：https://yangyuanlin.club
歡迎來踩~~~~

題目

• Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

題目大意

給定n對括號，編寫一個函數(shù)來生成所有的符合格式的括號組合。
上面給出了n = 3的例子。

思路

用遞歸來做。
注意幾點遞歸條件：
（1）左右括號均用完是遞歸出口；
（2）左括號沒有用完就加一個左括號；
（3）只有右括號少于左括號且右括號沒有用完時才能加右括號，因為不能出現(xiàn)“ ）（ ”這樣的情況。

• 關(guān)鍵：當(dāng)前位置左括號不少于右括號；
• 節(jié)點：目前位置左括號和右括號數(shù)（x,y）(x>=y)；
• 邊：從（x,y)到（x+1,y）和（x，y+1），x==y時，沒有（x,y+1）這條邊；
• 解：是從(0,0)出發(fā)到(n,n)的全部路徑。

代碼

#include<iostream>
#include<vector>
using namespace std;
void help_fun(int, int, string, vector<string >&);
vector<string> generateParenthesis(int n)
{
    vector<string > v;
    help_fun(n, n, "", v);
    return v;
}
void help_fun(int x, int y, string s, vector<string > &v)
{
    if(x == 0 && y == 0)
    {
        v.push_back(s);
        return;
    }
    if(x > 0)
        help_fun(x-1, y, s+"(", v);
    if(x<y && y>0)
        help_fun(x, y-1, s+")", v);
}
int main()
{
    vector <string > v;
    int n;
    cin >> n;
    v = generateParenthesis(n);
    for(int i=0; i<v.size(); i++)
    {
        cout<<v[i]<<endl;
    }
    return 0;
}

以上。

版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請注明出處。
個人博客地址：https://yangyuanlin.club
歡迎來踩~~~~