22. Generate Parentheses

In this tutorial we will solve 22. Generate Parentheses from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 22. Generate Parentheses

• Catalan Number Wikipeida
• Catalan Numbers - Numberphile YouTube

Problem statement

In this problem statement we are asked to generate all combinations of well-formed parentheses for integer input n that represents the number of pairs of parentheses.

By well-formed parentheses it means that an opening bracket must have matching closing bracket.

Example from leetcode.

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

Example 2:
Input: n = 1
Output: ["()"]

Constraints:

1 <= n <= 8

Approach

We can solve this problem using recursion. Alternatively, we can use the stack data structure to solve this problem.

In the following example we are solving the problem recursively.

We can create a generate function that will recursively build us a well-formed parentheses. We will start by calling the generate function with open counter set to 0, close counter set to 0 and parentheses set to empty string.

If open counter is equal to close counter and open+close is equal to 2n then, we will push the parentheses into the result.

If the open counter is less than n then we will recursively call the generate function with open+1, close and parentheses appended with '(' opening bracket.

If the close counter is less than open counter then we will recursively call the generate function with open, close+1 and parentheses appended with ')' closing bracket.

Let us say the input value of n = 2. So we will generate all well-formed parentheses.

n = 2, result = []

gen(open=0, close=0, parentheses='')
  -> is open === close && open + close === 2*n? no
  -> is open < n ? yes
    -> gen(open=1, close=0, parentheses='(')
      -> is open === close && open + close === 2*n? no
      -> is open < n ? yes
        -> gen(open=2, close=0, parentheses='((')
          -> is open === close && open + close === 2*n? no
          -> is open < n ? no
          -> is close < open ? yes
            -> gen(open=2, close=1, parentheses='(()')
  	          -> is open === close && open + close === 2*n? no
  	          -> is open < n ? no
  	          -> is close < open ? yes
                -> gen(open=2, close=2, parentheses='(())')
                  -> is open === close && open + close === 2*n? yes
                    -> save the parentheses in result
                    -> result is now ['(())']
  -> is close < open ? yes
    -> gen(open=1, close=1, parentheses='()')
      -> is open === close && open + close === 2*n? no
      -> is open < n ? yes
        -> gen(open=2, close=1, parentheses='()(')
          -> is open === close && open + close === 2*n? no
          -> is open < n ? no
          -> is close < open ? yes
            -> gen(open=2, close=2, parentheses='()()')
              -> is open === close && open + close === 2*n? yes
              -> save the parentheses in result
              -> result is now ['(())', '()()']

result = ['(())', '()()']

Code

JavaScript

Recursive approach

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = [];
    const gen = (open, close, acc) => {
        if (open === close && open + close === 2*n) {
            result.push(acc);
            return;
        }
        if (open < n) {
            gen(open + 1, close, `${acc}(`);
        }
        if (close < open) {
            gen(open, close + 1, `${acc})`);
        }
    };
    gen(0, 0, '');
    return result;
};

Iterative approach

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = [];
    const stack = [{ open: 0, close: 0, acc: '' }];

    while (stack.length > 0) {
        const { open, close, acc } = stack.pop();

        if (open === close && open + close === 2 * n) {
            result.push(acc);
            continue;
        }

        if (open < n) {
            stack.push({ open: open + 1, close: close, acc: `${acc}(` });
        }

        if (close < open) {
            stack.push({ open: open, close: close + 1, acc: `${acc})` });
        }
    }

    return result;
};

Complexity

Time complexity: O(4^n / √n)

The time complexity is determined by the number of valid sequences of n pairs of parentheses that can be generated is given by the nth Catalan number.

nth Catalan = (1/(n+1)) * (2n!/(n! * (2n - n)!))

The Catalan number grown asymptotically as ~ (4^n)/(n^(3/2))

Since string concatenation occurs in each step, and each string can have a maximum length of 2n, the cost per operation is O(n).

Total time complexity = O( (4^n)/(n^(3/2)) * n ) = O(4^n / √n)

Space complexity: O(4^n / √n)

The maximum number of elements in the stack corresponds to the Catalan number. Each sequence has a length of 2n. Then total space complexity = O( (4^n)/(n^(3/2)) * 2n ) = O(4^n / √n).