题解 | #括号生成#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        // 把括号插入上一次的答案中
        ArrayList<String> res = new ArrayList<>();
        if (n == 0)return res;
        if (n == 1) {
            res.add("()");
            return res;
        }
        ArrayList<String> prev = generateParenthesis(n - 1);
        Set<String> set = new HashSet<>();
        for (String str : prev) {
            gen(str,set);
        }
        res.addAll(set);
        return res;
    }

    private void gen(String str,Set<String> set) {
        set.add("()" + str);
        set.add(str + "()");
        for (int i = 0;i < str.length() - 1;i++) {
            set.add(str.substring(0,i + 1) + "()" + str.substring(i + 1,str.length()));
        }
    }
}