LeetCode Hot 100 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

方法二：回溯法
思路和算法

方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 ‘(’ 或 ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

class Solution {
public:void back(vector<string>& ans,string& cur,int open,int close,int n){if(cur.size() == n * 2){ans.push_back(cur);return;}if(open < n){cur.push_back('(');back(ans,cur,open + 1,close,n);cur.pop_back();}if(close < open){cur.push_back(')');back(ans,cur,open ,close + 1,n);cur.pop_back();}}vector<string> generateParenthesis(int n) {vector<string> ans;string cur;back(ans,cur,0,0,n);return ans;}
};