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:

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

 

解题思路：

DFS

class Solution { public:     vector<string> generateParenthesis(int n) {         vector<string>res;         if(n==0)return res;         dfs(res,n,0,0,"");         return res;     }     void dfs(vector<string>&res,int n,int l,int r,string s){         if(l==n&&r==n){             res.push_back(s);             return ;         }         if(l==n){             dfs(res,n,l,r+1,s+")");             return ;         }         if(l==r){             dfs(res,n,l+1,r,s+"(");             return ;         }         dfs(res,n,l+1,r,s+"(");         dfs(res,n,l,r+1,s+")");               } };