LeetCode Problems

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

Reference: 22. Generate Parentheses

- Catalan Number Wikipeida
- Catalan Numbers - Numberphile YouTube

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
```

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 = ['(())', '()()']
```

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;
};
```

**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).

ADVERTISEMENT