Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Given n = 3
, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
LeetCode上的原题,请参见我之前的博客Generate Parentheses。
解法一:
class Solution { public: /** * @param n n pairs * @return All combinations of well-formed parentheses */ vector<string> generateParenthesis(int n) { if (n == 0) return {}; vector<string> res; helper(n, n, "", res); return res; } void helper(int left, int right, string out, vector<string>& res) { if (left < 0 || right < 0 || left > right) return; if (left == 0 && right == 0) { res.push_back(out); return; } helper(left - 1, right, out + "(", res); helper(left, right - 1, out + ")", res); } };
解法二:
class Solution { public: /** * @param n n pairs * @return All combinations of well-formed parentheses */ vector<string> generateParenthesis(int n) { set<string> res; if (n == 0) { res.insert(""); } else { vector<string> pre = generateParenthesis(n - 1); for (auto a : pre) { for (int i = 0; i < a.size(); ++i) { if (a[i] == '(') { a.insert(a.begin() + i + 1, '('); a.insert(a.begin() + i + 2, ')'); res.insert(a); a.erase(a.begin() + i + 1, a.begin() + i + 3); } } res.insert("()" + a); } } return vector<string>(res.begin(), res.end()); } };
本文转自博客园Grandyang的博客,原文链接:生成括号[LintCode] Generate Parentheses ,如需转载请自行联系原博主。