题解 | #牛圈围栏问题#

知识点：回溯

思路：使用一个集合来保存结果，需要知道的是理解题意很重要，其实就是括号的全排列，我们使用回溯的方式遍历输出即可

编程语言：java

import java.util.*;


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

    private void backtrack(List<String> res, StringBuilder path, int left,
                           int right) {
        if (left > right) {
            return;
        }

        if (left == 0 && right == 0) {
            res.add(path.toString());
            return;
        }

        if (left > 0) {
            path.append('(');
            backtrack(res, path, left - 1, right);
            path.deleteCharAt(path.length() - 1);
        }

        if (right > 0) {
            path.append(')');
            backtrack(res, path, left, right - 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}