问题描述
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
想法与实现
涉及到全排列之类的事情，第一个想到的是递归。这个应该是最基础的做法。在这个问题里约束大致有两个，一个是括号对的个数，这个由输入给出，另外一个就是括号的匹配问题，一定要先有左括号再有右括号。这个问题就很容易用递归的思想去做，对于字符串s而言，每次可以选择增加一个左括号，或者在可以匹配到左括号的情况下增加一个右括号。所以是一个类似深度优先搜索的情况。最后得到的就是所有的全排列。
class Solution
{
private:
vector<string> res;
int n;
void generateStr(int left, int right, string s, int rest)
{
if (left == n && right == n)
{
res.push_back(s);
return;
}
if (left != n)
generateStr(left + 1, right, s + "(", rest + 1);
if (right != n && rest - 1 >= 0)
generateStr(left, right + 1, s + ")", rest - 1);
return;
}
public:
vector<string> generateParenthesis(int n)
{
this->n = n;
dfs(1, 0, "(", 1);
return res;
}
};