/*
 * Key point: deepth first strategy
 *   I can't conceive this solution by myself. Refering from others.
 * To-Do: making sure the java parameter passing mechanism
 */

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        StringBuffer sb = new StringBuffer();
        sb.append("");
        return helper(n, 0, 0, sb);
    }
    
    //parameter: total pairs n, left parenthese left, right parenthese right, temp buffer temp
    public ArrayList<String> helper(int n, int left, int right, StringBuffer sb){
        ArrayList<String> result = new ArrayList<String>();
        
        if(left > n || right > n)
            return result;
        
        //Work has been done, adding current StringBuffer to result    
        if(left == n && right == n){
            result.add(sb.toString());
            return result;
        }
        
        //left parenthese "(" is not enough
        if(left < n){
            
            //adding a "(" to the end of string buffer sb
            StringBuffer temp = new StringBuffer(sb);
            temp.append("(");
            
            //call helper() recursively
            result.addAll( helper(n, left+1, right, temp) );
        }
        
        //only if right parenthese ")" is less than right parenthese ")"
        //we can add a ")"; otherwise, we shouldn't add ")".
        if(right < left){
            
            //adding a ")" to the end of string buffer sb
            StringBuffer temp = new StringBuffer(sb);
            temp.append(")");
            
            //call helper() recursively
            result.addAll( helper(n, left, right+1, temp) );
        }
        
        return result;
    }
}
@@ -3,174 +3,61 @@
 %0A * 
-Key point: deepth first strategy%0A *   I can't conceive this solution by myself. Refering from others.%0A * To-Do: making sure the java parameter passing mechanism
+Re-do this question, now dfsWorker() return void
 %0A */%0A
-%0A
 publ
@@ -134,16 +134,76 @@
 nt n) %7B%0A
+        ArrayList%3CString%3E result = new ArrayList%3CString%3E();%0A
         
@@ -206,26 +206,27 @@
     StringBu
-ff
+ild
 er sb = new 
@@ -233,18 +233,19 @@
 StringBu
-ff
+ild
 er();%0A  
@@ -254,31 +254,37 @@
     
-sb.append(%22%22);%0A
+%0A        if(n %3C= 0)%0A 
         
 retu
@@ -283,434 +283,265 @@
     
+   
 return 
-helper(n, 0, 0, sb);%0A
+result;%0A   
     
-%7D%0A
     
+ 
 %0A    
-//parameter: total pairs n, left parenthese left, right parenthese right, temp buffer temp%0A    public ArrayList%3CString%3E helper(int n, int left, int right, StringBuffer sb)%7B%0A        ArrayList%3CString%3E result = new ArrayList%3CString%3E();%0A        %0A        if(left %3E n %7C%7C right %3E n)%0A            return result;%0A        %0A        //Work has been done, adding current StringBuffer to result    
+    dfsWorker(n, result, sb, 0, 0);%0A        return result;%0A        %0A    %7D%0A    %0A    public void dfsWorker(int n, ArrayList%3CString%3E result, StringBuilder sb, int left, int right)%7B%0A        %0A        //%22exit%22 for recursive call
 %0A   
@@ -556,17 +556,21 @@
 left == 
-n
+right
  && righ
@@ -627,39 +627,32 @@
           return
- result
 ;%0A        %7D%0A    
@@ -670,63 +670,77 @@
   //
-left parenthese %22(%22 is not enough%0A        if(left %3C
+invalid combination%0A        if(left %3C right %7C%7C left %3E n %7C%7C right %3E
  n)
-%7B
 %0A   
@@ -740,32 +740,39 @@
  n)%0A            
+return;
 %0A            //a
@@ -772,107 +772,71 @@
     
-//adding a %22(%22 to the end of string buffer sb%0A            StringBuffer temp = new StringBuffer(sb);
+%0A        //condition that add '('    %0A        if(left %3C n)%7B    
 %0A   
@@ -844,28 +844,26 @@
         
-temp
+sb
 .append(
 %22(%22);%0A  
@@ -858,22 +858,13 @@
 end(
-%22(%22);%0A        
+'(');
     
@@ -880,71 +880,31 @@
     
-//call helper() recursively%0A            result.addAll( helper(n
+dfsWorker(n, result, sb
 , le
@@ -914,24 +914,16 @@
 1, right
-, temp) 
 );%0A     
@@ -927,305 +927,123 @@
     
-  %7D%0A
       
-  %0A        //only if right parenthese %22)%22 is less than right par
+sb.deleteCharAt(sb.l
 en
+g
 th
-ese %22)%22%0A        //we can add a %22)%22; otherwise, we shouldn't add %22)%22.%0A        if(right %3C left)%7B%0A            %0A            //adding a %22)%22 to the end of string buffer sb%0A            StringBuffer temp = new StringBuffer(sb);
+()-1);%0A        %7D%0A        %0A        //condition that add ')'%0A        if(right %3C left)%7B
 %0A   
@@ -1055,20 +1055,18 @@
     
-temp
+sb
 .append(
 %22)%22)
@@ -1065,11 +1065,11 @@
 end(
-%22)%22
+')'
 );%0A 
@@ -1083,84 +1083,31 @@
     
-%0A            //call helper() recursively%0A            result.addAll( helper(n
+dfsWorker(n, result, sb
 , le
@@ -1121,16 +1121,8 @@
 ht+1
-, temp) 
 );%0A 
@@ -1132,41 +1132,53 @@
     
-%7D%0A
     
-    %0A        return result;
+sb.deleteCharAt(sb.length()-1);%0A        %7D
 %0A   

solve Generate Parentheses question once again