022括号生成

 1 #include "000库函数.h"
 2 
 3 
 4 
 5 
 6 //使用回溯法，当左括号数量大于右括号数量，则可以放置右括号
 7 void recall(vector<string>&bracket, string s, int left, int right) {//bracket使用引用，确保其变化会被保留
 8     if (left > right)return;
 9     if (left == 0 && right == 0)bracket.push_back(s);
10     else {
11         if (left > 0)recall(bracket, s + '(', left-1, right);
12         if (right > 0)recall(bracket, s + ')', left, right-1);
13     }
14     
15 }
16 
17 vector<string> generateParenthesis(int n) {
18     vector<string>bracket;
19     if (n < 1)return bracket;
20     recall(bracket, "",n, n);
21     return bracket;
22         
23 }
24 
25 每找到一个左括号，就在其后面加一个完整的括号，最后再在开头加一个()，就形成了所有的情况，
26 需要注意的是，有时候会出现重复的情况，所以我们用set数据结构，好处是如果遇到重复项，不会加入到结果中
27 最后我们再把set转为vector即可
28 
29 vector<string> generateParenthesis(int n) {
30     set<string>t;
31     if (n == 0)t.insert("");
32     else {
33         vector<string>pre = generateParenthesis(n - 1);
34         for (auto a : pre) {
35             for (int i = 0; i < a.size(); ++i) {
36                 if (a[i] == '(') {
37                     a.insert(a.begin() + i + 1, '(');
38                     a.insert(a.begin() + i + 2, '）');
39                     t.insert(a);
40                     a.erase(a.begin() + i + 1, a.begin() + i + 3);
41                 }
42             }
43             t.insert("()" + a);
44         }
45         
46     }
47     return vector<string>(t.begin(), t.end());//强制类型转换
48 
49 }
50 
51 
52 void T022() {
53     vector<string>Res;
54     Res = generateParenthesis(3);
55     for (int i = 0; i < Res.size(); ++i)
56         cout << Res[i] << endl;
57 
58 }