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.
1using System;
2using System.Collections.Generic;
3
4class GenerateParentheses {
5 public static IList<string> GenerateParenthesis(int n) {
6 List<string> result = new List<string>();
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 static void Main() {
25 IList<string> parentheses = GenerateParenthesis(3);
26 foreach (string s in parentheses) {
27 Console.WriteLine(s);
28 }
29 }
30}This C# solution adopts a backtracking approach wherein we build strings by adding '(' and ')' where appropriate. We ensure at all times that the number of ')' never exceeds '(', ensuring valid parenthesis sequences are generated. The primary function 'GenerateParenthesis' triggers the recursive backtracking call with appropriate initial parameters.