腾讯括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

 

C++：

1、深搜

class Solution { public: void dfs(int level, int l, int r, vector<string> &solution, string s, int n){ if(2*n == level) solution.push_back(s); if(l <= n-1) dfs(level+1, l+1, r, solution, s+'(', n); if(l >= r+1&&r <= n-1) dfs(level+1, l, r+1, solution, s+')', n); } vector<string> generateParenthesis(int n) { vector<string> solution; dfs(0, 0, 0, solution, "", n); return solution; } };

2、迭代

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> re; if(n==0) return re; re.push_back(""); for(int i = 0; i < 2*n; i++){ vector<string> temp; for(int i = 0; i < re.size(); i++){ int l = 0, r = 0; for(char x:re[i]){ if(x == '(') l++; if(x == ')') r++; } if(l < n) temp.push_back(re[i]+'('); if(r+1<=l) temp.push_back(re[i]+')'); } re = temp; } return re; } };

3、宽搜

class Solution { public: vector<string> generateParenthesis(int n) { queue<string>re; re.push(""); int level=0; while (level++!=2*n){ int length=re.size(); for (int i=0; i<length; ++i){ string temp=re.front(); re.pop(); int l = 0, r = 0; for (auto y : temp){ if (y == '(') ++l; if (y == ')') ++r; } if (l<n) re.push(temp + '('); if (r<l) re.push(temp + ')'); } } vector<string>ans; while(!re.empty()){ ans.push_back(re.front()); re.pop(); } return ans; } };