题解 | #括号生成#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    private ArrayList<String> list = new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        if (n <= 0) {
            return list;
        }
        recursion(new StringBuilder(), 0, 0, n);
        return list;
    }
    
    public void recursion(StringBuilder sb, int left, int right, int n) {
        if (left > n) {
            return;
        }
        if (left < right) {
            return;
        }
        // 右括号放满即表示括号生产完毕
        if (right == n) {
            list.add(sb.toString());
            return;
        }
        // 当前位置可以考虑放左右括号
        // 如果左括号小于n，就可以放左括号
        if (left < n) {
            sb.append("(");
            recursion(sb, left + 1, right, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right < left) {
            sb.append(")");
            recursion(sb, left, right + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}