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

import java.util.*;


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

        dfs(0, 0, "", ans, n);

        String[] result = new String[ans.size()];
        return ans.toArray(result);
    }

    private void dfs(int l, int r, String t, List<String> ans, int n) {
        if (l < r || l > n || r > n) {
            return;
        }

        if (l == n && r == n) {
            ans.add(t);
            return;
        }

        dfs(l + 1, r, t + "(", ans, n);
        dfs(l, r + 1, t + ")", ans, n);
    }
}

编程语言是Java。

该题考察的是回溯算法和深度优先搜索（DFS）的应用。题目要求生成有效的括号组合，输入参数 n 表示括号对数。我们需要找到所有满足条件的括号组合，并将结果以字符串数组的形式返回。

代码的思路如下：

1. 在 generateParenthesis 方法中，创建一个空的字符串集合 ans 用于存储结果。
2. 调用 dfs 方法进行深度优先搜索，传入初始参数 0、0、空字符串 ""、结果集合 ans 和括号对数 n。
3. 在 dfs 方法中，首先判断左括号数量 l 是否小于右括号数量 r ，或者两者超过了括号对数 n 的限制。若满足任一条件，则直接返回。
4. 然后判断左括号数量 l 和右括号数量 r 是否都等于括号对数 n。若是，则表示找到了一个符合条件的括号组合，将其添加到结果集合 ans 中并返回。
5. 否则，递归调用 dfs 方法，并分别在下一层增加左括号和右括号，同时更新括号字符串 t。
6. 在 generateParenthesis 方法的末尾，将结果集合 ans 转换为字符串数组并返回。