22. 括号生成

       

        给定需要生成的括号对数n，要求生成所有合法的括号组合，即左右括号必须正确匹配（遵循编程语言的语法规则）。

解题思路：采用选择与不选的策略

• 选择时添加左括号
• 不选择时添加右括号
  需要注意：已生成的字符串必须始终满足左括号数量≥右括号数量。设当前左括号数为left，则剩余可用右括号数为2*n-left。添加规则如下：

1. 当left < n时，可以添加左括号
2. 当剩余右括号数 > left时（即2*n-left > left），可以添加右括号

class Solution {
public:vector<string> ans;void dfs(int i,int m,int left,string &path) {if (i == m) {//括号构造完毕ans.push_back(path);return;}if (left < m / 2) {path[i] = '(';//选左括号dfs(i + 1,m,left + 1,path);}if (i - left < left) {path[i] = ')';//选右括号dfs(i + 1,m,left,path);}}vector<string> generateParenthesis(int n) {int m = 2 * n;string path(m,0);dfs(0,m,0,path);return ans;}
};