package advanced.combinatorial.combination.lc022_generateparentheses;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
 * For example, given n = 3, a solution set is:
 *  [
 *      "((()))",
 *      "(()())",
 *      "(())()",
 *      "()(())",
 *      "()()()"
 *  ]
 */
public class Solution {

    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return Arrays.asList("");
        }
        if (n == 1) {
            return Arrays.asList("()");
        }

        /*Set<String> curr = new HashSet<>();
        for (int i = 1; i < n/2; i++) {
            List<String> p1 = generateParenthesis(i);
            List<String> p2 = generateParenthesis(n-i);

            curr.add(p1 + p2);
            curr.add(p2 + p1);
        }*/

        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (String p1 : generateParenthesis(i)) {
                for (String p2 : generateParenthesis(n-i-1)) {
                    result.add("(" + p1 + ")" + p2);
                }
            }
        }
        return result;
    }

}

@@ -134,19 +134,120 @@
 va.util.
-Lis
+HashSet;%0Aimport java.util.LinkedList;%0Aimport java.util.List;%0Aimport java.util.Queue;%0Aimport java.util.Se
 t;%0A%0A/**%0A
@@ -531,16 +531,36 @@
 tion %7B%0A%0A
+    // My 2AC: O(?)%0A
     publ
@@ -600,24 +600,774 @@
 is(int n) %7B%0A
+        Queue%3CString%3E queue = new LinkedList%3C%3E();%0A        Set%3CString%3E result = new HashSet%3C%3E();%0A        queue.offer(%22%22);    // error1: start from () will error for n=1, since Set is empty%0A        while (n-- %3E 0) %7B%0A            result.clear(); // error2: don't forget clear%0A            for (int size = queue.size(); size %3E 0; size--) %7B%0A                String par = queue.poll();%0A                for (int i = 0; i %3C= par.length(); i++) %7B%0A                    String newpar = par.substring(0, i) + %22()%22 + par.substring(i);%0A                    if (result.add(newpar))%0A                        queue.offer(newpar);%0A                %7D%0A            %7D%0A        %7D%0A        return new ArrayList%3C%3E(result);%0A    %7D%0A%0A    public List%3CString%3E generateParenthesis1(int n) %7B%0A
         if (

leetcode-022 generate parentheses