题解 | 括号生成

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
     ArrayList<String> res = new ArrayList<>();
     int n = 0;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        this.n = n;
        backTrace(new StringBuilder(), 0, 0);
        return res;
    }

    private void backTrace(StringBuilder sb, int left, int right) {
        if (sb.length() == 2 * n) {
            if (left == right) {
                res.add(sb.toString());
            }
            return;
        }

        if (left < n) { // 当左括号不够时 优先选择左括号
            sb.append("(");
            backTrace(sb, left+1, right);
            sb.deleteCharAt(sb.length()-1);
        }

        if (right < left) { // 右括号 小于左括号时 选择右括号
            sb.append(")");
            backTrace(sb, left, right+1);
            sb.deleteCharAt(sb.length()-1);
        }

    }
}