Repository: TheAlgorithms/Java
Pull request #5096 (2024-04-04 14:29:31)

Implement Parentheses Generator
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

TruongNhanNguyen: > Two questions (just questions, I want to know your reasons):
> 
> * why did you use `List<String>` and not another container? (maybe set),
> * what do you think about marking methods of `ParenthesesGenerator` as `static`?
> 
> In general the code looks good.

1. The `List<String>` data structure was chosen for its simplicity and efficiency in this implementation. Using a `List` allows us maintain the order of generated parentheses combinations, which might be desirable for certain use cases. While a `Set<String>` could ensure uniqueness of combinations, it might not preserve the order of generation, which could be important depending on the application requirements.

2. Marking the methods of `ParenthesesGenerator` as static could be appropriate depending on the intended usage and design considerations. If the methods do not rely on instance-specific state or behavior, marking them as static could enhance code readability and usage simplicity. Static methods can be called without needing to instantiate an object of the class, which can be beneficial in scenarios where the class serves primarily as a utility or helper. However, if the methods need access to instance variables or if there is a possibility of different instances requiring different behaviors, then keeping them as instance methods would be more appropriate.
TruongNhanNguyen: I will change `ParathensesGenerator`'s methods to `static` later. Appreciate your questions.

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index a75b5213..36989c41 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -15,6 +15,7 @@
             * [MazeRecursion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/MazeRecursion.java)
             * [MColoring](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/MColoring.java)
             * [NQueens](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/NQueens.java)
+            * [ParenthesesGenerator](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/ParenthesesGenerator.java)
             * [Permutation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/Permutation.java)
             * [PowerSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/PowerSum.java)
             * [WordSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/WordSearch.java)
diff --git a/src/main/java/com/thealgorithms/backtracking/ParenthesesGenerator.java b/src/main/java/com/thealgorithms/backtracking/ParenthesesGenerator.java
new file mode 100644
index 00000000..8bbed410
--- /dev/null
+++ b/src/main/java/com/thealgorithms/backtracking/ParenthesesGenerator.java
@@ -0,0 +1,50 @@
+package com.thealgorithms.backtracking;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * This class generates all valid combinations of parentheses for a given number of pairs using backtracking.
+ */
+public final class ParenthesesGenerator {
+    private ParenthesesGenerator() {
+    }
+
+    /**
+     * Generates all valid combinations of parentheses for a given number of pairs.
+     *
+     * @param n The number of pairs of parentheses.
+     * @return A list of strings representing valid combinations of parentheses.
+     * @throws IllegalArgumentException if n is less than 0.
+     */
+    public static List<String> generateParentheses(final int n) {
+        if (n < 0) {
+            throw new IllegalArgumentException("The number of pairs of parentheses cannot be nagative");
+        }
+        List<String> result = new ArrayList<>();
+        generateParenthesesHelper(result, "", 0, 0, n);
+        return result;
+    }
+
+    /**
+     * Helper function for generating all valid combinations of parentheses recursively.
+     *
+     * @param result  The list to store valid combinations.
+     * @param current The current combination being formed.
+     * @param open    The number of open parentheses.
+     * @param close   The number of closed parentheses.
+     * @param n       The total number of pairs of parentheses.
+     */
+    private static void generateParenthesesHelper(List<String> result, final String current, final int open, final int close, final int n) {
+        if (current.length() == n * 2) {
+            result.add(current);
+            return;
+        }
+        if (open < n) {
+            generateParenthesesHelper(result, current + "(", open + 1, close, n);
+        }
+        if (close < open) {
+            generateParenthesesHelper(result, current + ")", open, close + 1, n);
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/backtracking/ParenthesesGeneratorTest.java b/src/test/java/com/thealgorithms/backtracking/ParenthesesGeneratorTest.java
new file mode 100644
index 00000000..9da16061
--- /dev/null
+++ b/src/test/java/com/thealgorithms/backtracking/ParenthesesGeneratorTest.java
@@ -0,0 +1,33 @@
+package com.thealgorithms.backtracking;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.List;
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class ParenthesesGeneratorTest {
+    @ParameterizedTest
+    @MethodSource("regularInputStream")
+    void regularInputTests(int input, List<String> expected) {
+        assertEquals(expected, ParenthesesGenerator.generateParentheses(input));
+    }
+
+    @ParameterizedTest
+    @MethodSource("negativeInputStream")
+    void throwsForNegativeInputTests(int input) {
+        assertThrows(IllegalArgumentException.class, () -> ParenthesesGenerator.generateParentheses(input));
+    }
+
+    private static Stream<Arguments> regularInputStream() {
+        return Stream.of(Arguments.of(0, List.of("")), Arguments.of(1, List.of("()")), Arguments.of(2, List.of("(())", "()()")), Arguments.of(3, List.of("((()))", "(()())", "(())()", "()(())", "()()()")),
+            Arguments.of(4, List.of("(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()")));
+    }
+
+    private static Stream<Arguments> negativeInputStream() {
+        return Stream.of(Arguments.of(-1), Arguments.of(-5), Arguments.of(-10));
+    }
+}