Generate Valid Parentheses Combinations

Problem Statement:
Given an integer n, generate all combinations of well-formed parentheses with n pairs.

---

Approach

We can use a recursive function to explore different possibilities for forming valid parentheses. The function keeps track of the number of opening and closing brackets, as well as the temporary string formed during the process.

Recursive Function (calculate):

• Parameters:

  • open_brackets: Number of opening brackets used so far.
  • close_brackets: Number of closing brackets used so far.
  • n: Total number of pairs required.
  • s: A list to store valid parentheses combinations.
  • t: Temporary string to build the current combination.

• Base Case:

  • If open_brackets and close_brackets are both equal to n, append t to the list s and return.

• Recursive Steps:

  1. If open_brackets is less than n, add an opening bracket ( to t and recursively call the function with open_brackets + 1.
  2. If close_brackets is less than open_brackets, add a closing bracket ) to t and recursively call the function with close_brackets + 1.

---

Main Function (generateParenthesis):

1. Initialize an empty list result.
2. Call the calculate function with initial parameters:
   • open_brackets = 0, close_brackets = 0, n, result, and an empty string t.
3. Return the list result containing all valid parentheses combinations.

---

Example Walkthrough

Example Input:

n = 3

Execution:

• The recursive function generates combinations step-by-step:
  • ((()))
  • (()())
  • (())()
  • ()(())
  • ()()()

Output:

["((()))", "(()())", "(())()", "()(())", "()()()"]

---

Test Cases

Test Case 1:

Input:
n = 1

Output:
["()"]

---

Test Case 2:

Input:
n = 2

Output:
["(())", "()()"]

---

Test Case 3:

Input:
n = 3

Output:
["((()))", "(()())", "(())()", "()(())", "()()()"]

---

Test Case 4: Edge Case

Input:
n = 0

Output:
[]

---

Complexity Analysis

Time Complexity:

• The number of valid parentheses combinations is the n-th Catalan number, which grows exponentially.
• Therefore, the time complexity is O(4^n / √n).

Space Complexity:

• The space complexity is O(n) due to the recursion stack.

— Written by Saurabh Patil • B.Tech CSE • Software Developer