-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGenerate Parentheses.cpp
More file actions
34 lines (30 loc) · 911 Bytes
/
Generate Parentheses.cpp
File metadata and controls
34 lines (30 loc) · 911 Bytes
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
29
30
31
32
33
34
// https://oj.leetcode.com/problems/generate-parentheses/
class Solution {
// nr_open/nr_close: # of open/close paranthesis generated
void do_generate(vector<string> &ret, string &buf, int nr_open, int nr_close, int n) {
if (nr_open + nr_close == 2 * n) {
ret.push_back(buf);
return;
}
if (nr_open < n) {
buf.push_back('(');
do_generate(ret, buf, nr_open + 1, nr_close, n);
buf.pop_back();
}
if (nr_open > nr_close) {
buf.push_back(')');
do_generate(ret, buf, nr_open, nr_close + 1, n);
buf.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ret;
if (n <= 0) {
return ret;
}
string buf;
do_generate(ret, buf, 0, 0, n);
return ret;
}
};