-
Notifications
You must be signed in to change notification settings - Fork 0
/
generateParenthess.cc
98 lines (89 loc) · 2.31 KB
/
generateParenthess.cc
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (!n) return vector<string>();
vector<string> ret;
recur(n, n, ret, "");
return ret;
}
void recur(int left, int right, vector<string> &ret, string tmp) {
if (!right) {
ret.push_back(tmp);
return;
}
if (right > left) recur(left, right - 1, ret, tmp + ")");
if (left) recur(left - 1, right, ret, tmp + "(");
}
//------------------------------------//
vector<string> generateParenthesis(int n) {
if (!n) vector<string>();
return _gen(n, n);
}
vector<string> _gen(int left, int right) {
if (!right) return vector<string>(1, "");
vector<string> ret;
if (left > 0) {
vector<string> tmp = _gen(left - 1, right);
for (int i = 0; i < tmp.size(); ++i) {
tmp[i] = "(" + tmp[i];
}
ret.insert(ret.end(), tmp.begin(), tmp.end());
}
if (left < right) {
vector<string> tmp1 = _gen(left, right - 1);
for (int i = 0; i < tmp1.size(); ++i) {
tmp1[i] = ")" + tmp1[i];
}
ret.insert(ret.end(), tmp1.begin(), tmp1.end());
}
return ret;
}
/*
vector<string> generateParenthesis(int n) {
vector<string> ret;
if (n <= 0)
return ret;
return recursion(n, n);
}
vector<string> recursion(int left, int right) {
//if (left == 0 && right == 0)
//return ret;
vector<string> ret;
if (right == 0 && left ==0) {
string tmp("");
ret.push_back(tmp);
return ret;
}
vector<string> tmp;
if (right > 0) {
tmp = recursion(left, right - 1);
for (int i = 0; i < tmp.size(); ++i) {
string tmp1(")");
tmp[i] = tmp[i] + tmp1;
ret.push_back(tmp[i]);
}
}
if (left > right) {
tmp = recursion(left - 1, right);
for (int i = 0; i < tmp.size(); ++i) {
string tmp1("(");
tmp[i] = tmp[i] + tmp1;
ret.push_back(tmp[i]);
}
}
return ret;
}
*/
};
int main(int argc, char** argv) {
Solution sol;
vector<string> tmp = sol.generateParenthesis(3);
for (int i = 0; i < tmp.size(); ++i) {
cout << tmp[i] << endl;
}
return 1;
}