LietCode
Generate Parentheses

Generate Parentheses

Abhi's photo
Abhi
·

3 min read

Great! Let's move on to the next problem.

Explain the Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example:

Input: n = 3

Output:

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

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

  1. Recursive Function: We'll create a helper function that adds an opening or closing parenthesis to the current combination.

  2. Valid Parentheses: Ensure that at any point, the number of closing parentheses does not exceed the number of opening parentheses.

  3. Backtracking: If the current combination reaches the required length (2 * n), we add it to the result list.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function generateParentheses(n) {
  const result = [];

  // Helper function for backtracking
  function backtrack(current, open, close) {
    // If the current combination is of the required length, add it to the result
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }

    // If we can add an opening parenthesis, do it
    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }

    // If we can add a closing parenthesis, do it
    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  }

  // Start the backtracking with an empty combination
  backtrack('', 0, 0);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have pairs of parentheses, and you want to generate all possible ways to arrange them such that they are balanced (every opening parenthesis has a matching closing parenthesis).

  • Recursive Function: This is like a helper that tries to form balanced combinations by adding opening or closing parentheses.

  • Valid Parentheses: This means ensuring that you never have more closing parentheses than opening ones at any point.

  • Backtracking: This means if the current combination doesn't lead to a balanced arrangement, you go back and try a different arrangement.

For each step, you can add an opening parenthesis if you haven't used up all n opening parentheses. You can add a closing parenthesis if the number of closing parentheses is less than the number of opening ones. If you form a valid combination (length 2 * n), you save it. If not, you undo your last step and try another option.

Code Explanation in Pointers

  1. Initialize Result Array: Create an empty array to store all combinations.

  2. Define Backtracking Function: Create a recursive function to explore different combinations.

  3. Base Case - Combination Formed: If the current combination's length matches 2 * n, add it to the result.

  4. Add Opening Parenthesis: If the number of opening parentheses is less than n, add an opening parenthesis.

  5. Add Closing Parenthesis: If the number of closing parentheses is less than the number of opening ones, add a closing parenthesis.

  6. Recursive Call: Call the function recursively with the updated combination.

  7. Start Search: Start the search with an empty combination.

Complexity Analysis

  • Time Complexity: O(4^n / √n), the nth Catalan number. This is because we generate all valid combinations of parentheses.

  • Space Complexity: O(4^n / √n), due to the result array storing all combinations and the recursion stack.

backtracking