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:
"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:

The classic question from the Cracking the Code Interview. DFS is enough. Note that it is wrong when the number of ')' is more than '(' in the current string. e.g. ()()).

Code (updated 201309):

class Solution {
public:
void gp(string str,int l,int r, int &n, vector<string> &res){
if (l>n){return;}
if (l==n && r==n){
res.push_back(str);
}else{
gp(str+"(",l+1,r,n,res);
if (l>r){
gp(str+")",l,r+1,n,res);
}
}
}
vector<string> generateParenthesis(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> res;
if (n==0){return res;}
gp("",0,0,n,res);
return res;
}
};


1 comment:

1. Can u please explain the code? What is happening in each step? I am new to backtracking and recursion. So I find it difficult to trace the flow of control in the recursive calls.