22. Generate Parentheses

nullskill · nullskill · commit 29f5618f669c · 2023-08-03T21:53:16.000+03:00
diff --git a/lib/src/medium/22.generate_parentheses/main.dart b/lib/src/medium/22.generate_parentheses/main.dart
@@ -0,0 +1,28 @@
+/// The time and space complexity of this code is `O(4^n / √n)`
+
+class Solution {
+  List<String> generateParenthesis(int n) {
+    List<String> result = [];
+
+    _generate(result, "", 0, 0, n);
+
+    return result;
+  }
+
+  void _generate(List<String> result, String current, int open, int close, int n) {
+    if (current.length == n * 2) {
+      result.add(current);
+      return;
+    }
+    if (open < n) {
+      _generate(result, "$current(", open + 1, close, n);
+    }
+    if (close < open) {
+      _generate(result, "$current)", open, close + 1, n);
+    }
+  }
+}
+
+void main(List<String> args) {
+  print(Solution().generateParenthesis(3));
+}
diff --git a/lib/src/medium/22.generate_parentheses/problem.txt b/lib/src/medium/22.generate_parentheses/problem.txt
@@ -0,0 +1,21 @@
+22. Generate Parentheses
+https://leetcode.com/problems/generate-parentheses/
+
+Given n pairs of parentheses, write a function to generate 
+all combinations of well-formed parentheses.
+
+ 
+Example 1:
+
+Input: n = 3
+Output: ["((()))","(()())","(())()","()(())","()()()"]
+
+Example 2:
+
+Input: n = 1
+Output: ["()"]
+ 
+
+Constraints:
+
+1 <= n <= 8
