【题解】【排列组合】【回溯】【Leetcode】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:

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

思路：

有关Parentheses的题目也是比较常见的，除了Generate Parentheses还有Valid Parentheses，Longest Valid Parentheses

回溯用递归写是性价比最高的，基本思想就是从前往后填字符保证'('的个数不能比')'少，且'('的个数不能比n多

代码：

 1 void generateAtDepth(vector<string> &Parentheses, string &p, int lefts, int rights, int depth, int n){
 2     if(depth == 2*n-1){
 3         p[depth] = ')';
 4         Parentheses.push_back(p);
 5         return;//返回值为void的函数不能忘了return啊！
 6     }
 7     if(lefts < n){//注意不能出现((()
 8         p[depth] = '(';
 9         generateAtDepth(Parentheses, p, lefts+1, rights, depth+1, n);
10     }
11     if(lefts > rights){
12         p[depth] = ')';
13         generateAtDepth(Parentheses, p, lefts, rights+1, depth+1, n);
14     }
15 }
16 vector<string> generateParenthesis(int n) {
17     vector<string> Parentheses;
18     if(n < 1) return Parentheses;
19     string p(2*n, '*');//一定要指定初始化字符
20     generateAtDepth(Parentheses, p, 0, 0, 0, n);
21     return Parentheses;
22 }