22. 括号生成

问题转化为：现在有 2n 个位置，每个位置可以放置字符 ‘(‘ 或者 ‘)’，求生成所有可能的并且有效的括号组合

可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个。cur表示当前字符串状态
左右括号都能用完，说明是合法的，res中记录当前cur
剩下的左括号比右括号多，或者括号数量小于0，说明是不合法的，直接return
回溯：做选择，撤销选择

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res=[]
        choose=['(',')']
        def backtrack(left,right,cur):# 还可以放几个左括号/右括号，当前字符串的状态

            # 合法的情况
            if left==0 and right==0: # 左右括号都用完了，合法
                res.append(cur)
                return
            # 不合法的情况
            # 剩下的左括号比右括号多，或者括号数量小于0
            if left>right or left<0 or right<0:
                return

            # 回溯， 有两种写法
            # 写法1：以左括号为例
            cur=cur+choose[0] # 做选择 ，尝试放左括号
            backtrack(left-1,right,cur)  
            cur=cur[:-1]  #撤销选择
            # 写法2：以右括号为例，直接在backtrack中进行更新
            backtrack(left,right-1,cur+choose[1])
        backtrack(n,n,'')
        return res

class Solution {
public:
    vector <string> res;
    vector <string> choose{"(", ")"};

    void backtrack(string visited, int left, int right) {
        if (left == 0 && right == 0) {
            res.push_back(visited);
            return;
        }
        if (left > right || left < 0 || right < 0) {
            return;
        }

//        只有两种选择，分别列举即可
        visited.append(choose[0]);
        backtrack(visited, left - 1, right);
        visited.pop_back();

        visited.append(choose[1]);
        backtrack(visited, left, right - 1);
        visited.pop_back();

        // // 或者写成回溯框架
        // for (int i = 0; i < 2; ++i) {
        //     if (i == 0) {
        //         visited.append(choose[0]);
        //         backtrack(visited, left - 1, right);
        //     } else {
        //         visited.append(choose[1]);
        //         backtrack(visited, left, right - 1);
        //     }
        //     visited.pop_back();
        // }
    }

    vector <string> generateParenthesis(int n) {
        string visited;
        backtrack(visited, n, n);
        return res;
    }
};