one more backtracking solution

fishercoder1534 · fishercoder1534 · commit 505ea2b8869a · 2016-11-01T09:38:15.000-07:00
diff --git a/MEDIUM/src/medium/GenerateParentheses.java b/MEDIUM/src/medium/GenerateParentheses.java
@@ -32,5 +32,30 @@ public static void main(String...args){
         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);
+            }
+        }
     }
 }
