题解 | #牛圈围栏问题#

import java.util.*;


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

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

    private void backTracking(int n, int m, StringBuilder sb) {
        // 如果n和m都为0说明，左括号和右括号都已经生成完毕，添加到list集合中
        if (n == 0 && m == 0) {
            list.add(sb.toString());
        }
        // n代表左括号数量
        if (n > 0) {
            sb.append('(');
            backTracking(n - 1, m, sb);
            // 回溯法，关键操作，去掉上次添加的最后一个，递归和回溯组合使用
            sb.deleteCharAt(sb.length() - 1);
        }
        // 如果m>n,那么添加右括号，其实就是先左，后右，因为一开始m=n,然后n先左if语句，然后m>n做if语句
        if (m > n) {
            sb.append(')');
            backTracking(n, m - 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

本题知识点分析：

1.回溯法

2.递归

3.StringBuilder单线程最快

4.数组遍历

本题解题思路分析：

1.利用回溯法创建功能函数

2.如果n和m都为0说明，左括号和右括号都已经生成完毕，添加到list集合中

3.n代表左括号数量

4.如果m>n,那么添加右括号，其实就是先左，后右，因为一开始m=n,然后n先左if语句，然后m>n做if语句

5.回溯法，关键操作，去掉上次添加的最后一个，递归和回溯组合使用

本题使用编程语言: Java