问题描述:
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]问题分析:
由问题描述可知,所生成的圆括号序列中,左括号和右括号的数量是一致的,而且!序列生成时,每添加一个字符,左括号的数量总是不少于右括号的数量。因而可以考虑用递归的来实现,每次输出一个左括号或右括号,构造所有合法的输出结果的排列组合。代码实现如下:
class Solution { public: vector generateParenthesis(int n) { vector result; deepConstruct(n,n,"",result); return result; } void deepConstruct(int left,int right,string out,vector &result){ if(left==0&&right==0){ result.push_back(out); return; } if(left>right){ return; } if(left<=right){ if(left>0) deepConstruct(left-1,right,out+"(",result); if(right>0) deepConstruct(left,right-1,out+")",result); } } };时间:3ms(完全无法理解前面的那些再短时间的是如何做到的,也许考虑下不适用递归)