题解 | 括号生成

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    int left = 0;// 记录左括号当前数量，最多不能超过n
    int right = 0;// 记录右括号当前数量，最多不能超过left
    int n;
    StringBuilder sb = new StringBuilder();
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        this.n = n;
        helper();
        return res;
    }

    private void helper () {
	  // 终止条件
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
	// 左右括号分别回溯
        if (left < n) {
            sb.append('(');
            left++;
            helper();
            left--;
            sb.deleteCharAt(sb.length() - 1);
        }

        if (right < left) {
            sb.append(')');
            right++;
            helper();
            right--;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}