题解 | #牛圈围栏问题#

知识点

回溯

解题思路

首先，我们定义一个列表 fences，用于存储所有的围栏组合。

然后，我们使用回溯法来搜索所有的围栏组合。

在每一步中，我们可以选择放置一个木棍和两个铁链，或者放置一个铁链和一个木棍。如果放置后，当前的围栏组合仍然是合法的，则继续向下搜索。

当放置了 n 个木棍和 2n 个铁链后，表示已经生成了一个稳定的围栏组合，将围栏组合转换成字符串形式并将其加入到 fences 中。

递归结束后，将 fences 转换成字符串数组并返回结果。

Java题解

import java.util.*;


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

        return fences.toArray(new String[fences.size()]);
    }

    private void backtrack(int leftCount, int rightCount, StringBuilder current,
                           List<String> fences) {
        if (leftCount == 0 && rightCount == 0) {
            fences.add(current.toString());
            return;
        }

        if (leftCount > 0) {
            current.append("(");
            backtrack(leftCount - 1, rightCount, current, fences);
            current.deleteCharAt(current.length() - 1);
        }

        if (rightCount > leftCount) {
            current.append(")");
            backtrack(leftCount, rightCount - 1, current, fences);
            current.deleteCharAt(current.length() - 1);
        }
    }
}