# [leetcode] Generate Parentheses

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

`"((()))", "(()())", "(())()", "()(())", "()()()"`

tag: backtracking

7/10/2015 udpate

DFS approach, add some restrictions to guarantee the validation of parentheses

```class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string thisAns;
dfs(n, 0, 0, thisAns, ans);
return ans;
}
void dfs(int total, int left, int right, string& thisAns, vector<string>& ans){
//total - total numbers of parentheses
//left - number of left parentheses
//right - number of right parenthese
if(left + right == 2 * total){
ans.push_back(thisAns);
return ;
}
if(left == total){
//push right parenthese
thisAns.push_back(')');
dfs(total, left, right + 1, thisAns, ans);
thisAns.pop_back();
}else if(left > right){
//left < total
//left >= total
//push either left or right
thisAns.push_back('(');
dfs(total, left + 1, right, thisAns, ans);
thisAns.pop_back();

thisAns.push_back(')');
dfs(total, left, right + 1, thisAns, ans);
thisAns.pop_back();
}
else{
//left < total
//left == right
//push left
thisAns.push_back('(');
dfs(total, left + 1, right, thisAns, ans);
thisAns.pop_back();
}
}
};```

“()”

n=2时，向里面插入一对”()”，则有六种情况：

()()”, “(())”，”(())“, “(())”，”(())“，”()()

_generateParenthesis(int numOfLeftPar, int numOfRightPar, string thisRe)

numOfLeftPar为当前状态下还剩余的可用的左括号”(“数量；

numOfRightPar为当前状态下还剩余的可用的右括号”)”数量；

thisRe为当前状态下的尝试字符串；

```class Solution {
public:
vector<string> re;
vector<string> generateParenthesis(int n) {
string tmp;
_generateParenthesis(n, n, tmp);
return re;
}
void _generateParenthesis(int numOfLeftPar, int numOfRightPar, string thisRe){
if(numOfLeftPar == 0 && numOfRightPar == 0){//found one
re.push_back(thisRe);
}
else if(numOfLeftPar > numOfRightPar){// no valid result
return;
}
else{
if(numOfLeftPar > 0){ //insert a left parenthese
numOfLeftPar--;
thisRe.push_back('(');
_generateParenthesis(numOfLeftPar, numOfRightPar, thisRe);
thisRe.pop_back();
numOfLeftPar++;
}
if(numOfRightPar > 0){ // insert a right parenthese
numOfRightPar--;
thisRe.push_back(')');
_generateParenthesis(numOfLeftPar, numOfRightPar, thisRe);
thisRe.pop_back();
numOfRightPar++;
}
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.