括号生成
题目： 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
函数 myAtoi(string s) 的算法如下：
- 空格：读入字符串并丢弃无用的前导空格（" "）
- 符号：检查下一个字符（假设还未到字符末尾）为 ‘-’ 还是 ‘+’。如果两者都不存在，则假定结果为正。
- 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
- 舍入：如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。
返回整数作为最终结果。
输入格式：
输出格式：
输入样例：
输出样例：
1
| ["((()))","(()())","(())()","()(())","()()()"]
|
示例 1：
**输入：** n = 3
**输出：**["((()))","(()())","(())()","()(())","()()()"]
示例 2：
**输入：** n = 1
**输出：**["()"]
提示：
思路：
递归函数跟踪已使用的左括号和右括号数量，确保右括号数量不超过左括号，以维持有效性。当组合长度达到2*n时，保存结果。算法遍历所有可能状态，最终返回所有合法括号字符串的列表。
代码：
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
|
#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<string> result;
public:
void generate(int l, int r, string s){
if(l > r || r < 0 || l < 0) return;
if(l == 0 && r == 0) {
result.push_back(s);
return;
}
if(l == r) {
s.push_back('(');
generate(l-1, r, s);
}else {
s.push_back('(');
generate(l-1, r, s);
s[s.size()-1] = (')');
generate(l, r-1, s);
}
}
vector<string> generateParenthesis(int n) {
string s;
generate(n, n, s);
return result;
}
};
int main(void) {
int x = 3;
Solution s;
cout << s.generateParenthesis(x);
return 0;
}
|
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
|
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
int m = 2 * n;
vector<string> res;
string path(m, 0);
auto dfs = [&](this auto&& dfs, int left, int right) -> void
{
if(left + right == m)
{
res.push_back(path);
return;
}
if(left < n)
{
path[left + right] = '(';
dfs(left + 1, right);
}
if(right < left && right < n)
{
path[left + right] = ')';
dfs(left, right + 1);
}
};
dfs(0, 0);
return res;
}
};
class Solution {
void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
if (cur.size() == n * 2) {
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(ans, cur, open + 1, close, n);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
backtrack(ans, cur, open, close + 1, n);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
};
int main(void) {
int x = 3;
Solution s;
cout << s.generateParenthesis(x);
return 0;
}
|
