feat: add well-formed parentheses generator (TheAlgorithms#2445)

* feat: add well-formed parentheses generator * updating DIRECTORY.md * changes made * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update backtracking/generate_parentheses.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * chore: apply suggestions from code review * Update backtracking/generate_parentheses.cpp Co-authored-by: realstealthninja <68815218+realstealthninja@users.noreply.github.com> * updating DIRECTORY.md --------- Co-authored-by: github-actions[bot] <github-actions@users.noreply.github.com> Co-authored-by: David Leal <halfpacho@gmail.com> Co-authored-by: realstealthninja <68815218+realstealthninja@users.noreply.github.com>
ShuN6211 · May 16, 2023 · 6027480 · 6027480
1 parent 4b740d4
commit 6027480
Show file tree

Hide file tree

Showing 2 changed files with 116 additions and 0 deletions.
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -1,5 +1,6 @@
 
 ## Backtracking
+  * [Generate Parentheses](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/backtracking/generate_parentheses.cpp)
   * [Graph Coloring](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/backtracking/graph_coloring.cpp)
   * [Knight Tour](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/backtracking/knight_tour.cpp)
   * [Magic Sequence](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/backtracking/magic_sequence.cpp)
@@ -67,6 +68,7 @@
   * [Queue Using Two Stacks](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/queue_using_two_stacks.cpp)
   * [Rb Tree](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/rb_tree.cpp)
   * [Reverse A Linked List](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/reverse_a_linked_list.cpp)
+  * [Segment Tree](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/segment_tree.cpp)
   * [Skip List](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/skip_list.cpp)
   * [Sparse Table](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/sparse_table.cpp)
   * [Stack](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/stack.hpp)
@@ -228,6 +230,7 @@
   * [Prime Factorization](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/prime_factorization.cpp)
   * [Prime Numbers](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/prime_numbers.cpp)
   * [Primes Up To Billion](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/primes_up_to_billion.cpp)
+  * [Quadratic Equations Complex Numbers](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/quadratic_equations_complex_numbers.cpp)
   * [Realtime Stats](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/realtime_stats.cpp)
   * [Sieve Of Eratosthenes](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/sieve_of_eratosthenes.cpp)
   * [Sqrt Double](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/sqrt_double.cpp)

diff --git a/backtracking/generate_parentheses.cpp b/backtracking/generate_parentheses.cpp
@@ -0,0 +1,113 @@
+/**
+ * @file
+ * @brief Well-formed [Generated
+ * Parentheses](https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/794/) with all combinations.
+ *
+ * @details a sequence of parentheses is well-formed if each opening parentheses
+ * has a corresponding closing parenthesis
+ * and the closing parentheses are correctly ordered
+ *
+ * @author [Giuseppe Coco](https://github.com/WoWS17)
+
+ */
+
+#include <cassert>   /// for assert
+#include <iostream>  /// for I/O operation
+#include <vector>    /// for vector container
+
+/**
+ * @brief Backtracking algorithms
+ * @namespace backtracking
+ */
+namespace backtracking {
+/**
+ * @brief generate_parentheses class
+ */
+class generate_parentheses {
+ private:
+    std::vector<std::string> res;  ///< Contains all possible valid patterns
+
+    void makeStrings(std::string str, int n, int closed, int open);
+
+ public:
+    std::vector<std::string> generate(int n);
+};
+
+/**
+ * @brief function that adds parenthesis to the string.
+ *
+ * @param str string build during backtracking
+ * @param n number of pairs of parentheses
+ * @param closed number of closed parentheses
+ * @param open number of open parentheses
+ */
+
+void generate_parentheses::makeStrings(std::string str, int n,
+                                                     int closed, int open) {
+    if (closed > open)  // We can never have more closed than open
+        return;
+
+    if ((str.length() == 2 * n) &&
+        (closed != open)) {  // closed and open must be the same
+        return;
+    }
+
+    if (str.length() == 2 * n) {
+        res.push_back(str);
+        return;
+    }
+
+    makeStrings(str + ')', n, closed + 1, open);
+    makeStrings(str + '(', n, closed, open + 1);
+}
+
+/**
+ * @brief wrapper interface
+ *
+ * @param n number of pairs of parentheses
+ * @return all well-formed pattern of parentheses
+ */
+std::vector<std::string> generate_parentheses::generate(int n) {
+    backtracking::generate_parentheses::res.clear();
+    std::string str = "(";
+    generate_parentheses::makeStrings(str, n, 0, 1);
+    return res;
+}
+}  // namespace backtracking
+
+/**
+ * @brief Self-test implementations
+ * @returns void
+ */
+static void test() {
+    int n = 0;
+    std::vector<std::string> patterns;
+    backtracking::generate_parentheses p;
+
+    n = 1;
+    patterns = {{"()"}};
+    assert(p.generate(n) == patterns);
+
+    n = 3;
+    patterns = {{"()()()"}, {"()(())"}, {"(())()"}, {"(()())"}, {"((()))"}};
+
+    assert(p.generate(n) == patterns);
+
+    n = 4;
+    patterns = {{"()()()()"}, {"()()(())"}, {"()(())()"}, {"()(()())"},
+                {"()((()))"}, {"(())()()"}, {"(())(())"}, {"(()())()"},
+                {"(()()())"}, {"(()(()))"}, {"((()))()"}, {"((())())"},
+                {"((()()))"}, {"(((())))"}};
+    assert(p.generate(n) == patterns);
+
+    std::cout << "All tests passed\n";
+}
+
+/**
+ * @brief Main function
+ * @returns 0 on exit
+ */
+int main() {
+    test();  // run self-test implementations
+    return 0;
+}