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:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Subscribe to see which companies asked this question

一开始的想法是进行递归，n＝1的时候生成part＝（）
之后每上面一层，相当于给part进行包装，（）part，（part），part（）；
后来发现这种方法是有问题的。比如在n＝4时，”(())(())”无法产生，如代码注释的写法，于是查阅过资料后选择对part进行分解，即在part的每个空档插入“（）”，即可完成。


class Solution {
public:
vector generateParenthesis(int n) {
if(n<1) { vector sum;
return sum;
}
if(n == 1)
{
vector sum;
sum.push_back("()");
// sum.push_back(")(");
return sum;
}
else
{
vector sum;
vector temp = generateParenthesis(n-1);
//vector::iterator it;
for(int i = 0 ; i < temp.size();i++) { /* string now1 = "()"+ temp[i]; string now2 = "("+ temp[i]+")"; string now3 = temp[i]+"()"; sum.push_back(now1); sum.push_back(now2); sum.push_back(now3);*/ string pre_str=temp[i]; int pre_str_len=(int)pre_str.length(); for(int j=0;j<=pre_str_len;j++){ string now_str=pre_str.substr(0,j)+"()"+pre_str.substr(j,pre_str_len-j); sum.push_back(now_str); } string now_str=pre_str+"()"; sum.push_back(now_str); } std::sort( sum.begin(), sum.end() ); sum.erase( std::unique( sum.begin(), sum.end() ), sum.end() ); return sum; } } };

参考资料