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来做

l 记录剩余 '(' 数量

r 记录可以添加的 ')' 数量

只有当附加一个 '(' 后，才可以附加 '）'.

计数原则是：

初始时，l = n, r = 0.

str添加一个 '(', 则 l 减少 1，且可用 ')' 加1.

str添加一个 ')'，则 r 减少 1。

代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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