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

示例：

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

Solution

参考：《算法小抄》4.3

• 回溯算法

# @lc code=start
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if not n: return
        res = []
        track = []
        
        def backtrack(left, right, track):
            # 数量小于0，不合法
            if left<0 or right<0: return 
            # 左括号剩余大于右括号，不合法
            if right<left: return
            # 所有括号都刚好用完
            if left==0 and right==0:
                res.append(''.join(track))
                return
            
            track.append('(')
            backtrack(left-1, right, track)
            track.pop()
            
            track.append(')')
            backtrack(left, right-1, track)
            track.pop()
            
        backtrack(n, n, track)
        return res
# @lc code=end

cpp

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s = "";
        backtrack(n, n, s);
        return res;
    }
private:
    vector<string> res;

    void backtrack(int left, int right, string s) {
        if (left < 0 || right < 0) return;
        if (left > right) return;
        if (left == 0 && right == 0) {
            res.emplace_back(s);
        }
        s.push_back('(');
        backtrack(left-1, right, s);
        s.pop_back();

        s.push_back(')');
        backtrack(left, right-1, s);
        s.pop_back();

        return;
    }
};