版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：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对括号，编写一个函数来生成所有的符合格式的括号组合。
上面给出了n = 3的例子。
思路
用递归来做。
注意几点递归条件：
（1）左右括号均用完是递归出口；
（2）左括号没有用完就加一个左括号；
（3）只有右括号少于左括号且右括号没有用完时才能加右括号，因为不能出现“ ）（ ”这样的情况。
- 关键：当前位置左括号不少于右括号；
- 节点：目前位置左括号和右括号数（x,y）(x>=y)；
- 边：从（x,y)到（x+1,y）和（x，y+1），x==y时，没有（x,y+1）这条边；
- 解：是从(0,0)出发到(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;
}
以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
