给出 n 表明生成括号的对数,请你写出一个函数,使其可以生成全部可能的而且有效的括号组合。web
例如,给出 n = 3,生成结果为:算法
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
(right > left,即右括号比左括号多,必定不会出现匹配)
or '('的个数left 大于 n (left > n)
left == right && left == n
class Solution { public: vector<string> result; void backtrace(string& tmp,int l,int r,int n){ if(r > l || l > n) return; if(l == r && l == n){ result.push_back(tmp); return ; } tmp.push_back('('); backtrace(tmp,l+1,r,n); *tmp.rbegin() = ')'; // 把pop_back()与push_back()合在一块儿 backtrace(tmp,l,r+1,n); tmp.pop_back(); } vector<string> generateParenthesis(int n) { string tmp; backtrace(tmp,0,0,n); return result; } };