题解 | #牛圈围栏问题#

import java.util.*;


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

    private void backtrack(List<String> result, String current, int openCount, int closeCount, int n) {
        if (current.length() == 2 * n) {
            result.add(current);
            return;
        }

        if (openCount < n) {
            backtrack(result, current + "(", openCount + 1, closeCount, n);
        }
        if (closeCount < openCount) {
            backtrack(result, current + ")", openCount, closeCount + 1, n);
        }
    }
    
}

知识点分析：

1. 回溯算法：通过递归生成所有可能的括号组合。
2. 递归：在每一步中，通过添加 '(' 或 ')' 来扩展当前的括号序列。
3. 限制条件：在生成括号序列时，需要满足每个位置上的 ')' 数量不超过对应位置上的 '(' 数量。

解题思路：

在代码中，我们通过回溯算法递归地生成所有可能的括号组合。每次递归调用时，我们可以选择添加 '(' 或 ')'，但需要确保不违反限制条件。当括号序列长度达到 2 * n 时，我们将其加入结果列表中。