generate parenthesis

fishercoder1534 · fishercoder1534 · commit 1aba850a0893 · 2016-10-31T09:21:36.000-07:00
diff --git a/MEDIUM/src/medium/GenerateParentheses.java b/MEDIUM/src/medium/GenerateParentheses.java
@@ -0,0 +1,36 @@
+package medium;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import utils.CommonUtils;
+
+public class GenerateParentheses {
+    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){
+        GenerateParentheses test = new GenerateParentheses();
+        int n = 3;
+        List<String> result = test.generateParenthesis(n);
+        CommonUtils.print(result);
+    }
+}
diff --git a/README.md b/README.md
@@ -63,6 +63,7 @@
 |43|[Multiply Strings](https://leetcode.com/problems/multiply-strings/)|[Solution]|||Medium
 |24|[Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)|[Solution](../../blob/master/EASY/src/easy/SwapNodesinPairs.java)|O(n)|O(1)|Easy| Recursion, LinkedList
 |23|[Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)|[Solution](../../blob/master/HARD/src/hard/MergeKSortedList.java)|O(n*logk)|O(logk)|Hard|Heap
+|22|[Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)|[Solution](../../blob/master/MEDIUM/src/medium/GenerateParentheses.java)|TBD|O(n)|Medium|Backtracking
 |21|[Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)|[Solution](../../blob/master/EASY/src/easy/MergeTwoSortedLists.java)|O(n)|O(1)|Easy|
 |20|[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)|[Solution](../../blob/master/EASY/src/easy/ValidParentheses.java)|O(n)|O(n)|Easy|Stack
 |17|[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)|[Solution](../../blob/master/MEDIUM/src/medium/LetterCombinationsofaPhoneNumber.java)|O(n*4^n)|O(n)|Medium|Backtracking
