[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:

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

思路：

通过向string插入"("和")"直到两者的数量都为n，则一个combination构建完成。如何保证这个combination是well-formed？在插入过程中的任何时候：

1. 只要"("的数量没有超过n，都可以插入"("。
2. 而可以插入")"的前提则是当前的"("数量必须要多余当前的")"数量。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> allComb; string comb; findParenthesis(n, 0, 0, comb, allComb); return allComb; } void findParenthesis(int n, int nleft, int nright, string &comb, vector<string> &allComb) { if(nleft==n && nright==n) { allComb.push_back(comb); return; } if(nleft<n) { comb.push_back('('); findParenthesis(n, nleft+1, nright, comb, allComb); comb.pop_back(); } if(nright<nleft) { comb.push_back(')'); findParenthesis(n, nleft, nright+1, comb, allComb); comb.pop_back(); } } };