题解 | #括号生成#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> ans = new ArrayList<>();
        dfs(ans, n, 0, 0, new StringBuilder());
        return ans;
    }
    private void dfs(ArrayList<String> ans, int n, int left, int right,
                     StringBuilder sb) {
        if (left == n && right == n) {
            ans.add(sb.toString());
            return;
        }
	  // 如果左括号数量小于n，可以使用左括号
        if (left < n) {
            sb.append("(");
            dfs(ans, n, left + 1, right, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
	  // 如果右括号数量小于n且小于左括号数量，可以使用右括号，必须要保证先使用左括号（在左右括号数量相等的情况下）
        if (right < n && left > right) {
            sb.append(")");
            dfs(ans, n, left , right + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}