题解 | 括号生成

import java.util.*;


public class Solution {
private ArrayList<String> ans = new ArrayList<>();

    /**
     * 生成所有有效的括号组合
     *
     * @param n 生成括号的对数
     * @return 包含所有有效括号组合的ArrayList
     */
    public ArrayList<String> generateParenthesis(int n) {
        // 使用StringBuilder来构建括号组合
        StringBuilder sb = new StringBuilder();
        // 回溯方法，传入左右括号剩余数量和当前构建的字符串
        backtrack(n, n, sb);
        // 返回所有有效的括号组合结果
        return ans;
    }

    /**
     * 使用回溯法生成有效的括号组合
     *
     * @param left  剩余可用的左括号数量
     * @param right 剩余可用的右括号数量
     * @param sb    当前正在构建的字符串
     */
    private void backtrack(int left, int right, StringBuilder sb) {
        // 如果左右括号都用完了，将当前组合加入结果集
        if (left == 0 && right == 0) {
            ans.add(new String(sb));
            return;
        }

        // 如果剩余左括号多于右括号，无法形成有效组合，直接返回
        if (left > right) {
            return;
        }

        // 如果左括号或右括号数量为负数，无效情况，直接返回
        if (left < 0 || right < 0) {
            return;
        }
        // 尝试添加左括号
        sb.append('(');
        backtrack(left - 1, right, sb);
        sb.deleteCharAt(sb.length() - 1); // 回溯，删除最后添加的左括号

        // 尝试添加右括号
        sb.append(')');
        backtrack(left, right - 1, sb);
        sb.deleteCharAt(sb.length() - 1); // 回溯，删除最后添加的右括号
    }
}