package advanced.combinatorial.combination.lc022_generateparentheses;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * 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 static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.generateParenthesis(3));
    }

    // 3AC
    public List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        //generate(ret, "", n, 0);
        generate(ret, "", 0, 0, n);
        return ret;
    }

    private void generate(List<String> ret, String par, int open, int close, int max) {
        for (int i = 0; i < par.length(); i++) System.out.print("\t");
        System.out.printf("open=%d close=%d par=%s\n", open, close, par);
        if (par.length() == max * 2) {
            ret.add(par);
            return;
        }
        if (open < max) generate(ret, par + "(", open + 1, close, max);
        if (close < open) generate(ret, par + ")", open, close + 1, max);
    }

    // My 2AC: O(?)
    public List<String> generateParenthesis2(int n) {
        Queue<String> queue = new LinkedList<>();
        Set<String> result = new HashSet<>();
        queue.offer("");    // error1: start from () will error for n=1, since Set is empty
        while (n-- > 0) {
            result.clear(); // error2: don't forget clear
            for (int size = queue.size(); size > 0; size--) {
                String par = queue.poll();
                for (int i = 0; i <= par.length(); i++) {
                    String newpar = par.substring(0, i) + "()" + par.substring(i);
                    if (result.add(newpar))
                        queue.offer(newpar);
                }
            }
        }
        return new ArrayList<>(result);
    }

    public List<String> generateParenthesis1(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;
    }

}

@@ -682,19 +682,8 @@
  %7D%0A%0A
-    // 3AC%0A
     
@@ -785,18 +785,16 @@
         
-//
 generate
@@ -803,43 +803,23 @@
 et, 
-%22%22, n, 0);%0A        generate(ret, %22%22
+new char%5Bn * 2%5D
 , 0,
@@ -823,16 +823,19 @@
  0, 0, n
+, 0
 );%0A     
@@ -904,39 +904,39 @@
 et, 
-String pa
+char%5B%5D st
 r, int 
-open
+left
 , int 
-close
+right
 , in
@@ -940,16 +940,23 @@
  int max
+, int i
 ) %7B%0A    
@@ -963,180 +963,139 @@
     
-for (int i = 0; i %3C par.length(); i++) System.out.print(%22%5Ct%22);%0A        System.out.printf(%22open=%25d close=%25d par=%25s%5Cn%22, open, close, par);%0A        if (par.length() == max * 2
+if (left == max && right == left) %7B%0A            ret.add(String.valueOf(str));%0A            return;%0A        %7D%0A%0A        if (left %3C max
 ) %7B%0A
@@ -1110,20 +1110,20 @@
     
-ret.add(par)
+str%5Bi%5D = '('
 ;%0A  
@@ -1136,171 +1136,191 @@
     
-return;%0A        %7D%0A        if (open %3C max) generate(ret, par + %22(%22, open + 1, close, max);%0A        if (close %3C open) generate(ret, par + %22)%22, open, close + 1, max);
+generate(ret, str, left + 1, right, max, i + 1);%0A        %7D%0A        if (right %3C left) %7B%0A            str%5Bi%5D = ')';%0A            generate(ret, str, left, right + 1, max, i + 1);%0A        %7D
 %0A   

leetcode 022: generate parenthesis