题解 | #牛圈围栏问题#

知识点：回溯

这是一道经典的括号匹配问题，对于左右括号来说，都有可能出现，左括号根据总括号对数进行添加，右括号根据左括号的个数进行添加，每增加一个字符，就可以根据以上两种情况进行判断，分别增加对应的字符，当左右括号个数都达到最大个数后，即可将其字符串保存起来作为一种情况，回溯遍历所有情况即可得到答案。

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);
        }
    }
}