题解 | #牛圈围栏问题#

题目考察的知识点是：

本题主要考察知识点是递归、回溯。

题目解答方法的文字分析：

使用回溯算法生成所有可能的括号组合。在每个位置上，可以选择添加左括号或右括号。通过递归调用回溯函数，在选择添加左括号和右括号的过程中，不断向结果列表中添加新的完整括号组合。需要注意的是，添加左括号的数量不能超过n，添加右括号的数量不能超过左括号的数量。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


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

    public String[] generateParenthesis (int n) {
        // write code here
        backTracking(n, n, new StringBuilder());
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void backTracking(int n, int m, StringBuilder sb) {
        if (n == 0 && m == 0) {
            list.add(sb.toString());
        }
        if (n > 0) {
            sb.append('(');
            backTracking(n - 1, m, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (m > n) {
            sb.append(')');
            backTracking(n, m - 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}