题解 | #牛圈围栏问题#

知识点：

DFS/剪枝/回溯

分析：

1. 首先，代码中定义了两个全局变量：vector<string> res用于存储生成的所有有效括号组合，string path用于暂时存储正在生成的括号组合。
2. 接下来，代码定义了一个dfs函数，用于进行深度优先搜索。它有四个参数：u: 表示已经放置的左括号数量。l: 表示剩余可用的左括号数量。r: 表示剩余可用的右括号数量。idx: 表示当前递归的深度。
3. 在dfs函数中，首先检查当前括号组合的长度是否达到了2 * u，如果是，则说明已经放置了n对有效括号，将该组合添加到结果向量res中，并返回。
4. 接着，代码进入两个条件判断块：如果l > 0，表示还可以放置左括号。代码将一个左括号放入path中，然后通过递归调用dfs函数，将l减1（表示放置了一个左括号），u加1（表示放置了一个左括号），并将idx加1。递归完成后，回溯（backtrack）并将刚刚放置的左括号从path中移除。如果l < r，表示当前放置的左括号数量少于右括号。代码将一个右括号放入path中，然后通过递归调用dfs函数，将r减1（表示放置了一个右括号），u加1（表示放置了一个左括号），并将idx加1。递归完成后，回溯并将刚刚放置的右括号从path中移除。
5. 最后，函数返回存储在res中的所有有效括号组合作为结果。

编程语言：

C++

完整代码：

    vector<string> res;
    string path;
    void dfs(int u,int l,int r,int idx){
        if(path.size() == u * 2){
            res.push_back(path);return;
        }
        if(l > 0){
            path.push_back('(');
            dfs(u,l - 1,r,idx+1);
            path.pop_back();
        }
        if(l < r){
            path.push_back(')');
            dfs(u,l,r - 1,idx+1);
            path.pop_back();
        }    
    }
    vector<string> generateParenthesis(int n) {
        dfs(n,n,n,0);
        return res;
    }