Java 题解 | #牛圈围栏问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串一维数组
     */
    private List<String> res = new ArrayList<>();
    private StringBuilder path = new StringBuilder();

    private void dfs(int u, int l, int r, int idx) {
        if (path.length() == u * 2) {
            res.add(path.toString());
            return;
        }
        if (l > 0) {
            path.append('(');
            dfs(u, l - 1, r, idx + 1);
            path.deleteCharAt(path.length() - 1);
        }
        if (l < r) {
            path.append(')');
            dfs(u, l, r - 1, idx + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public String[] generateParenthesis(int n) {
        dfs(n, n, n, 0);
        String[] result = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

编程语言是Java。

该题考察的知识点包括：

• 递归
• 字符串操作
• 列表（ArrayList）的使用

代码的文字解释如下：

1. 定义一个字符串构建器 path，用于构建每种括号组合。
2. 实现一个递归函数 dfs，接受四个参数：u 表示需要生成的括号对数，l 表示当前已有的左括号数，r 表示当前已有的右括号数，idx 表示当前所在位置的索引。
3. 在递归函数 dfs 中，首先判断是否已经生成了指定数量的括号对（即 path.length() 是否等于 u * 2），如果是，则将当前括号组合添加到结果列表 res 中，并返回。
4. 分别处理两种情况：如果左括号数还未达到指定数量，可以在当前位置添加一个左括号，并递归调用 dfs 函数增加左括号数；如果左括号数小于右括号数（即还有可以匹配的左括号），可以在当前位置添加一个右括号，并递归调用 dfs 函数增加右括号数。
5. 在递归函数 dfs 中，完成每次递归后需要的清理工作，即将当前位置的括号删除（通过 path.deleteCharAt(path.length() - 1)）。
6. 实现 generateParenthesis 方法，接受一个整数 n 作为参数，并返回生成的括号组合数组。
7. 在 generateParenthesis 方法中，调用递归函数 dfs 来生成括号组合。