LeetCode 22: Generate Parentheses solution, TypeScript

This summer I took a break from side projects and gave LeetCode a try. It’s been nearly 3 years since my data structures and algorithms course with OSU, so I wanted to give myself a refresher on solving these kinds of problems.

This particular problem, “Generate Parenthesis“, was challenging for me at first but I revisited it a couple times over the summer and on the most recent try, I developed a solution that I think is fairly simple to understand, so I wanted to share it here. (I admit it’s not the most performant solution, but it passes.)

The premise

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

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 8

My solution

I started this problem by writing out what would be generated when n =1, when n = 2, when n = 3, and when n = 4. This step helped me to better understand what I needed to generate and it gave me an essential opportunity to spot patterns, which I did.

When n = 0
result = [""]

When n = 1
result = ["()"]

When n = 2
result = ["()(), (())"]

When n = 3
result = ["()()()","((()))","()(())","(())()"]

When n = 4
result = ["()()()()","(((())))","(()(()))","((())())","()((()))","((()))()","()()(())","()(())()","(())()()"]

The pattern:

I noticed that every time I generated a new result, I was building on the previous n value’s result array.

Specifically, the steps are:

  1. Take each result in the previous n value’s array and wrap it in parentheses. Each of those “wrapped” results becomes part of the new n value’s results array.
  2. Take each result in the previous n value’s results array and insert a new “()” at each possible location in the string. Each of those “inserted” results becomes part of the new n value’s results array.

You might realize at this point that some duplicate results will be generated during this process. This is why I put the results into a Set (so that duplicates are ignored).

Here is this approach, written in TypeScript:

function generateParenthesis(n: number): string[] {
    if (n === 1) { return ["()"]; }
    
    let result = new Set<string>();
    let previousCombos = generateParenthesis(n-1);
    
    for (let i in previousCombos) {
        let combo = previousCombos[i];
        
        // wrap all previous entries in parens and put those in the set
        result.add("("+combo+")");
        
        // now step through each one and embed a new paren at each possible position
        for (let i = 0; i < combo.length; i++) {
            result.add(combo.substring(0,i) + '()' + combo.substring(i));
        }
    }
    
    return [...result];
};

View as a gist on Github

Runtime analysis

Honestly, I don’t fully understand the runtime on this one, since it’s recursive and since each subsequent step draws from a growing list of “previous step” solutions. It “feels” exponential, but it’s not quite – or at least, the quantity of results in the sets that I worked out by hand is not increasing exponentially.

Pressed to come up with something, I’d say it’s O(2n) because:

  • We have to “handle” every 1…n (that’s the first n)
  • And every time we “handle” an n, we have to produce n * x results, where x is the length of the previous n’s results and that length grows (considerably) with each step.

From this article, “The growth curve of an O(2n) function is exponential – starting off very shallow, then rising meteorically.”

Hey, that sounds like this problem… right?

(If you know how to figure this one out with greater accuracy I’d love to hear it in the comments.)

Performance

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.