题解 | #括号生成#

import java.util.ArrayList;
import java.util.HashSet;


public class Solution {
    private final HashSet<String> result = new HashSet<>(); // 用Set实现去重
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        if(n==0) return new ArrayList<>();
        dg("", 0, 0, n);
        return new ArrayList<>(result);
    }

    private void dg(String s, int l, int r, int n){
        if(n==l && n==r){ // 左右括号已经用完
            result.add(s); // 添加到结果集
            return;
        }
        if(l < n) { // 还有(
            dg("("+s, l+1, r, n);
            dg(s + "(", l + 1, r, n);

        }
        if(r < l){ // 右括号比左括号少
            dg(s+")", l, r+1, n);
        }
    }
}