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 see what I needed to generate and it gave me an opportunity to spot patterns.
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:
- 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.
- 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];
// 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];
};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
[Update] 1 year later: a dynamic programming solution
November 2022 – I showed this blog to a friend and he developed a neat solution that builds a 2D array where each index holds all of the previous step’s calculations. What’s clever about this solution is that it does not generate duplicates the way my Set-based solution above does.
function nextPermutation(previousPermutations: string[][]): string[] {
const nextPermutationsLength = previousPermutations.length;
let nextPermutations = [];
for (let i = 0; i < nextPermutationsLength; i++) {
// each of the previous permutations becomes our "inner" permutations (array)
const innerPermutations = previousPermutations[i];
// calculate how many outer permutations we need based on where we are in the loop
const outerPermutationsLength = nextPermutationsLength - 1 - i;
// grab from that position to get "outer permutations"
const outerPermutations = previousPermutations[outerPermutationsLength];
// now that we have the outer permutations, step through them...
let newPermutations = outerPermutations.flatMap(outer => innerPermutations.map(inner => `(${inner})${outer}`));
newPermutations.forEach((newPerm) => {
nextPermutations.push(newPerm);
})
}
return nextPermutations;
}
function generateParenthesis(n: number): string[] {
let result = [[""]];
for (let i = 1; i < n+1; i++) {
// push the array of new permutations into the result array
result.push(nextPermutation(result));
}
// result[n] now holds the array we need...
return result[n];
};
