题解 | #牛圈围栏问题#

考察的是回溯算法的应用。

通过左括号的数量来控制。如果左括号数量不大于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);//0 0 分别代表左括号和右括号的数量 初始为0
        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);
        }
    }
}