题解 | #牛圈围栏问题#

题目考察的知识点

考察回溯算法

题目解答方法的文字分析

需要注意左括号必须先于右括号出现，总体括号数量受限制于n。确定下来之后就可以写程序了。如果能继续添加括号就加入左括号，当左括号数量大于右括号的时候才选择添加右括号。通过左右括号的数量在回溯算法中进行组合的控制。具体细节看代码实现。

本题解析所用的编程语言

使用Java语言解答

完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串一维数组
     */
    public String[] generateParenthesis (int n) {
        // write code here
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans.toArray(new String[ans.size()]);
    }
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) { //判断是否能添加括号
            ans.add(cur.toString());
            return;
        }
        if (open < max) { //添加左括号
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}