递归/回溯：Generate Parentheses生成合法括号

已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能。 例如:n = 3
结果为: ["((()))", “(()())”, “(())()”, “()(())”, “()()()”]

首先思考如何生成所有的括号组合的可能性，即例如2组括号，总共4个符号组合的可能型，那么每个位置就有两种括号的可能性，要么左括号，要么右括号，此时可以写出如代码：

void generate(string item, int n, std::vector<string> &result) {if (item.size() == 2 * n) {result.push_back(item);return ;}generate(item + "(", n , result);generate(item + ")", n , result);
} std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate("", n, result);return result;
}

测试如上代码,可以看到2组括号总共可能有16中组合的可能性:

2
((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))

但是根据输出结果，我们显然能够看出来很多结果并不符合 合法括号的要求，那么什么是合法的括号呢？或者说如何生成一个合法的括号呢？

根据括号的规律：

1. 初始括号一定是左括号
2. 括号集中左括号的数目一定和右括号的数目相等
3. 添加括号的过程中如果左括号的数目大于右括号，则才能够添加右括号，否则不能添加右括号

基于以上过程，实现如下:

/*left和right代表剩余括号数，left代表还剩下多少个左括号未添加，right代表还剩下多少个右括号未添加*/
void generate_leagal(string item, int left, int right, std::vector<string> &result) {if(left == 0 && right == 0) {result.push_back(item);return;}if(left > 0) { //当还有剩余的左括号未添加，则添加左括号generate_leagal(item + "(", left - 1, right, result);}if (left < right) { //当已添加的左括号的数目大于右括号，则才能够添加右括号generate_leagal(item + ")", left, right - 1, result);}
}std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate_leagal("", n, n, result);return result;
}

测试代码如下:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>/*
已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能。 例如:n = 3
结果为: ["((()))", "(()())", "(())()", "()(())", "()()()"]
*/using namespace std;void generate_leagal(string item, int left, int right, std::vector<string> &result) {if(left == 0 && right == 0) {result.push_back(item);return;}if(left > 0) {generate_leagal(item + "(", left - 1, right, result);}if (left < right) {generate_leagal(item + ")", left, right - 1, result);}
}std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate_leagal("", n, n, result);return result;
}int main(int argc, char const *argv[])
{int n;std::vector<string> result;cin >> n;result = generate_parenthesed(n);for (int i = 0;i < result.size(); ++i) {cout << result[i] << endl;}return 0;
}

输出如下:

#输入
4
#输出
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

总结

以上是生活随笔为你收集整理的递归/回溯：Generate Parentheses生成合法括号的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。