题解 | #牛圈围栏问题#

题目考察的知识点:回溯

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

使用回溯算法生成所有可能的括号组合。
通过递归调用回溯函数，选择添加左括号和右括号
需要注意的是，添加右括号的数量不能超过左括号的数量。

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

本题解析所用的编程语言: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);
        }
    }
}