题目描述
给出 n 代表生成括号的对数, 请你写出一个函数, 使其能够生成所有可能的并且有效的括号组合.
例如, 给出 n =3, 生成结果为:
- ["((()))",
- "(()())",
- "(())()",
- "()(())",
- "()()()"
- ]
解题思路
利用回溯的思想递归的生成括号. 具体来说记录当前剩余左括号数 left, 剩余右括号数 right, 当前的生成括号字符串 s, 进行如下操作:
若 left 为 0, 说明左括号已全部打印完, 所以将剩余的右括号全部打印出来并加入到结果集
若 right>left, 即当前字符串中的左括号还有未匹配到的右括号, 此时有两种选择: 继续打印一个左括号或者匹配打印一个右括号, 再对这两种选择分别递归判断
若 left 和 right 相等, 即当前字符串中的左括号全部有匹配到的右括号, 此时只能再打印一个左括号, 再递归判断
代码
- class Solution {
- public:
- vector<string> generateParenthesis(int n) {
- vector<string> res;
- generate(n, n, "", res);
- return res;
- }
- void generate(int left, int right, string s, vector<string> &res){
- if(left == 0){
- while(right--)
- s += ")";
- res.push_back(s);
- }
- else if(right> left){
- generate(left-1, right, s+"(", res);
- generate(left, right-1, s+")", res);
- }
- else
- generate(left-1, right, s+"(", res);
- }
- };
来源: http://www.bubuko.com/infodetail-2618492.html