题解 | #括号生成#

vector<string> res;
void backtrack(int n,int left,int right,string &path){
    //left==right==n，表示先判断left==right然后将结果与n做判断，这样是不对的
    //left==n&&right==n才是正确的
    //终止条件，左括号和右括号都等于n时，满足条件
    if(left==n&&right==n){
        res.push_back(path);
        return ;
    }
    //当左括号小于n时，就可以选择左括号
    if(left<n){
        //这里的递归回溯逻辑没捋清楚，还需要再想想
        path.push_back('(');
        backtrack(n, left+1, right, path);
        path.pop_back();
    }
    //当右括号小于n并且右括号数量小于左括号数量就可以选择右括号
    if(right<n&&left>right){
        path.push_back(')');
        backtrack(n, left, right+1, path);
        path.pop_back();
    }
}
vector<string> generateParenthesis(int n) {
    string path;
    backtrack(n, 0, 0, path);
    return res;
}

backtrack(n, left, right+1, path+')');