数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例： 输入：n = 3 输出：[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
我的代码：
class Solution { public: int left_n; int right_n; stack<char> input; vector<char> per_compose; vector<string>ans; vector<string> generateParenthesis(int n) { if(n==0) return ans; left_n=n-1; right_n=n; input.push('('); per_compose.push_back('('); dfs(n,1); return ans; } void dfs(int n,int depth) { if(per_compose.size()==(2*n)) { string s; for(int i=0;i<per_compose.size();i++) s+=per_compose[i]; ans.push_back(s); return ; } if(right_n>=1) { if(!input.empty()&&input.top()=='(') { per_compose.push_back(')'); right_n--; input.pop(); dfs(n,depth+1); per_compose.pop_back(); right_n++; input.push('('); } } if(left_n>=1) { per_compose.push_back('('); input.push('('); left_n--; dfs(n,depth+1); per_compose.pop_back(); input.pop(); left_n++; } } };网上优秀的代码：
class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; func(res, "", 0, 0, n); return res; } void func(vector<string> &res, string str, int l, int r, int n){ if(l > n || r > n || r > l) return ; if(l == n && r == n) {res.push_back(str); return;} func(res, str + '(', l+1, r, n); func(res, str + ')', l, r+1, n); return; } };解题思路就是dfs。看到题目的第一反应也是用dfs解决，因为感觉就是列出所有的组合，从中寻找满足要求的组合，只能用图遍历算法。然后回想起来，当遇到的问题是全排列问题的时候，最好是选择dfs而不是bfs，因为可以省空间，所以选择dfs。 看了看我自己的代码和大佬的代码。同样都是dfs，大佬的代码就要简洁很多。主要是省掉了很多的变量，像我写的时候，用了left_n保存(括号的使用情况，right_n保存)括号的使用情况，还有per_compose这个vector保存每一种组合方式。但是其实这些变量都可以通过dfs函数的参数体现出来，完全不用自己再重新定义变量。还有中间的剪枝，下面这份代码直接用if(l > n || r > n || r > l) return ;就考虑到了所有的剪枝。r > l这个判断条件就很精妙，省掉了很多的代码量。
