数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。用c++代码来实现
时间: 2024-09-13 17:05:46 浏览: 31
实习二之括号配对_括号配对C++代码_
在 C++ 中,可以使用递归回溯算法来生成所有有效的括号组合。下面是一个简单的实现示例:
```cpp
#include <iostream>
#include <vector>
std::string generateParenthesis(int n) {
std::string result;
std::vector<char> buffer(n, '()');
backtrack(result, buffer, 0, n);
return result;
}
void backtrack(std::string &result, std::vector<char> &buffer, int open, int close) {
if (open == close && close <= n / 2) {
result += buffer.begin(), buffer.end();
// 如果已经填满开放括号并达到闭合括号的一半,则添加到结果中
std::cout << "Generated: " << result << std::endl;
} else if (open < close) {
// 未填完开放括号,继续添加左括号
buffer[open] = '(';
backtrack(result, buffer, open + 1, close);
// 回溯,尝试其他情况
buffer[open] = ')';
backtrack(result, buffer, open + 1, close);
} else if (open > close) {
// 已经填满了开放括号,尝试添加右括号来关闭剩余的括号
buffer[close] = ')';
backtrack(result, buffer, open, close - 1);
}
}
int main() {
int n = 3; // 例如,n=3 将生成如 (()()), (()) 和 ()() 这样的有效组合
for (int i = 0; i <= n; ++i) {
std::cout << "n=" << i << ": " << generateParenthesis(i) << std::endl;
}
return 0;
}
```
这个函数会打印出所有长度从0到n的有效括号组合。`backtrack` 函数通过递归地尝试添加括号,然后回溯来保证每个括号都是配对的。
阅读全文