Sponsored
Sponsored
The key idea here is to build the solution by choosing either an opening or a closing parenthesis at each step. We make sure that any partial solution is valid - at any point in time, the number of closing parentheses cannot exceed the number of opening ones. We also stop adding parentheses when we have used 'n' of each.
Time Complexity: O(4^n/sqrt(n)) due to the Catalan number growth.
Space Complexity: O(n) for recursion stack.
1import java.util.ArrayList;
2import java.util.List;
3
4public class GenerateParentheses {
5 public static List<String> generateParenthesis(int n) {
6 List<String> result = new ArrayList<>();
7 backtrack(result, "", 0, 0, n);
8 return result;
9 }
10
11 private static void backtrack(List<String> result, String current, int open, int close, int max) {
12 if (current.length() == max * 2) {
13 result.add(current);
14 return;
15 }
16 if (open < max) {
17 backtrack(result, current + "(", open + 1, close, max);
18 }
19 if (close < open) {
20 backtrack(result, current + ")", open, close + 1, max);
21 }
22 }
23
24 public static void main(String[] args) {
25 List<String> parentheses = generateParenthesis(3);
26 for (String s : parentheses) {
27 System.out.println(s);
28 }
29 }
30}The Java solution uses a backtracking technique where we expand our current string by adding either an opening or a closing parenthesis based on constraints. We maintain two counters for open and closed parentheses and make recursive calls as long as our current solution is valid. This ensures that we only construct valid parentheses sequences during generation.