package com.fishercoder.solutions;

import com.fishercoder.common.utils.CommonUtils;

import java.util.ArrayList;
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 _22 {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    void backtrack(List<String> result, String str, int left, int right, int max) {
        if (str.length() == max * 2) {
            result.add(str);
            return;
        }

        if (left < max) {
            backtrack(result, str + "(", left + 1, right, max);
        }

        if (right < left) {
            backtrack(result, str + ")", left, right + 1, max);
        }
    }

    public static void main(String... args) {
        _22 test = new _22();
        int n = 3;
        List<String> result = test.generateParenthesis(n);
        CommonUtils.print(result);

        Solution2 sol2 = new Solution2();
        List<String> result2 = sol2.generateParenthesis(n);
        CommonUtils.print(result2);
    }

    static class Solution2 {
        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList();
            if (n == 0) {
                return result;
            }
            helper(result, "", n, n);
            return result;
        }

        void helper(List<String> result, String par, int left, int right) {
            if (left > 0) {
                helper(result, par + "(", left - 1, right);
            }
            if (right > left) {
                helper(result, par + ")", left, right - 1);
            }
            if (right == 0) {
                result.add(par);
            }
        }
    }
}

@@ -134,16 +134,51 @@
 st;%0A%0A/**
+%0A * 22. Generate Parentheses%0A *%0A * 
 Given n 
@@ -273,17 +273,21 @@
 theses.%0A
-%0A
+ *%0A *
  For exa
@@ -403,24 +403,64 @@
 class _22 %7B%0A
+    public static class Solution1 %7B%0A    
     public L
@@ -500,32 +500,36 @@
 nt n) %7B%0A        
+ 
+   
 List%3CString%3E res
@@ -543,32 +543,36 @@
 ew ArrayList();%0A
+    
         backtrac
@@ -595,32 +595,36 @@
  0, n);%0A        
+    
 return result;%0A 
@@ -622,27 +622,35 @@
 result;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     void bac
@@ -725,24 +725,28 @@
 ) %7B%0A        
+  
+  
 if (str.leng
@@ -768,32 +768,36 @@
 ) %7B%0A            
+    
 result.add(str);
@@ -813,16 +813,20 @@
     
+ 
+   
 return;%0A
     
@@ -821,16 +821,20 @@
 return;%0A
+    
         
@@ -836,32 +836,36 @@
      %7D%0A%0A        
+    
 if (left %3C max) 
@@ -858,32 +858,36 @@
  (left %3C max) %7B%0A
+    
             back
@@ -942,27 +942,34 @@
         
-%7D%0A%0A
+    %7D%0A%0A   
         
 if (righ
@@ -952,32 +952,33 @@
   %7D%0A%0A           
+ 
 if (right %3C left
@@ -973,32 +973,36 @@
 right %3C left) %7B%0A
+    
             back
@@ -1061,355 +1061,41 @@
     
-%7D%0A
     %7D%0A
-%0A
     
-public static void main(String... args) %7B%0A        _22 test = new _22();%0A        int n = 3;%0A        List%3CString%3E result = test.generateParenthesis(n);%0A        CommonUtils.print(result);%0A%0A        Solution2 sol2 = new Solution2();%0A        List%3CString%3E result2 = sol2.generateParenthesis(n);%0A        CommonUtils.print(result2);%0A    %7D%0A%0A   
+    %7D%0A    %7D%0A%0A    public
  sta

refactor 22