# 22. 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:

``````[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
``````

Difficulty: Medium

``````(
((
(((
((()
((())
((()))
(()())
~
()()()
``````

DFS(深度优先),这里可以想象成左括号优先

### 解法1

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
generateParenthesisDFS(n,n,"",res);
return res;
}
void generateParenthesisDFS(int left,int right,string out,vector<string>& res)
{
if (left>right) return;
if (left==0 && right==0) res.push_back(out);
else{
if (left>0) generateParenthesisDFS(left-1,right,out+'(',res);
if (right>0) generateParenthesisDFS(left,right-1,out+')',res);
}
}
};
``````

### 解法2

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
generateParenthesisDFS(n,0,0,"",res);
return res;
}
void generateParenthesisDFS(int n,int x,int y,string out,vector<string>& res)
{
if (y==n) res.push_back(out);
if (x<n) generateParenthesisDFS(n,x+1,y,out+'(',res);
if (x>y) generateParenthesisDFS(n,x,y+1,out+')',res);
}
};
``````

comments powered by Disqus