已知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 
#include 
#include 
#include /*
已知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
#输出
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()