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 }
【题解】【排列组合】【回溯】【Leetcode】Generate Parentheses
原文：http://www.cnblogs.com/wei-li/p/GenerateParentheses.html