package code;
/*
 * 22. Generate Parentheses
 * 
 * Medium
 * String, Backtracking
 * 
 * n=422
 *      lc32, lc22, lc301
 */
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class  lc22 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis2(4));
    }

    public static List generateParenthesis(int n) {
        //
        Set res = new HashSet();
        if(n==1) {
            res.add("()");
            return new ArrayList(res);
        }
        List temp = generateParenthesis(n-1);
        // n-1
        for (int i = 0; i < temp.size(); i++) {
            res.add("("+temp.get(i)+")");
            res.add("()"+temp.get(i));
            res.add(temp.get(i)+"()");
        }
        //2
        for (int j = 2; j