Generate Parentheses

• medium
• backtracking
• Problem URL

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

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Solution

Use backtracking to generate all possible combinations of parentheses. Start with an empty string and add a ( if the number of open parentheses is less than n and add a ) if the number of close parentheses is less than the number of open parentheses. If the length of the current string is equal to n * 2, add the current string to the result.

Implementation

JavaScript

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let max = n * 2;
  const result = [];
  var backtrack = function (current, open, close) {
    if (current.length === max) {
      result.push(current);
      return;
    }

    if (open < n) {
      backtrack(current + "(", open + 1, close);
    }

    if (close < open) {
      backtrack(current + ")", open, close + 1);
    }
  };
  backtrack("", 0, 0, result);
  return result;
};

TypeScript

function generateParenthesis(n: number): string[] {
  let max = n * 2;
  const result: string[] = [];
  function backtrack(current: string, open: number, close: number) {
    if (current.length === max) {
      result.push(current);
      return;
    }

    if (open < n) {
      backtrack(current + "(", open + 1, close);
    }

    if (close < open) {
      backtrack(current + ")", open, close + 1);
    }
  }
  backtrack("", 0, 0);
  return result;
}

Go

func generateParenthesis(n int) []string {
  max := n * 2
  result := make([]string, 0)
  backtrack("", 0, 0, max, n, &result)
  return result
}

func backtrack(current string, open int, close int, max int, n int, result *[]string) {
  if len(current) == max {
    *result = append(*result, current)
    return
  }

  if open < n {
    backtrack(current+"(", open+1, close, max, n, result)
  }

  if close < open {
    backtrack(current+")", open, close+1, max, n, result)
  }
}

Pseudocode

Main function

1. Create a variable max and set it to n * 2
2. Create an empty array result
3. Create a function backtrack that takes current, open, close as arguments
4. Call the backtrack function with an empty string "", 0, and 0

Backtracking function

1. Check if the length of the current string is equal to max. If it is, add the current string to the result and return

2. If the number of open parentheses is less than n, call the backtrack function with the current string concatenated with an open parentheses (, open + 1, and close

3. If the number of close parentheses is less than the number of open parentheses, call the backtrack function with the current string concatenated with a close parentheses ), open, and close + 1

Complexity Analysis

• The time complexity of this algorithm is O(4^n / sqrt(n)) because for each of the 2n positions, we can either put an open or close parentheses, giving us 2^2n possibilities. However, not all these possibilities are valid. We use the Catalan number to estimate the number of valid combinations, which is O(4^n / sqrt(n))

• The space complexity of this algorithm is O(4^n / sqrt(n)) because we are using recursion and the maximum depth of the recursion tree is 2n