[leetcode] 22. 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, Backtracking

分析:

采取回溯法,基于深度优先策略遍历所有括号排列的可能性,唯一的限制在于,当栈为空时,只能插入左括号。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class  {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
backtrack(res, "", n, n, 0);
return res;
}
void backtrack(vector<string> &res, const string &prev, int l_left, int r_left, int total) {
if (l_left == 0) {
res.push_back(prev + string(r_left, ')'));
return;
}
backtrack(res, prev+"(", l_left-1, r_left, total+1);
if (total > 0) // only when there are left parentheses in stack, can we input a right parenthesis.
backtrack(res, prev+")", l_left, r_left-1, total-1);
}
};