Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
To generate every possible solution, we should start with the empty string ""
, and repeatedly add opened and closed parentheses until we visit every solution.
1. We can add an open parenthesis "("
if we've added fewer than n of them so far.
2. We can add a closed parenthesis ")"
if there are fewer closed parentheses than open parentheses so far.
Using these rules, we can build a function that visits all the possible solutions.
Our function needs to keep track of the current string we have, parentheses
. We also need it to know the number of open and closed parentheses it's used so far, o
and c
.
1. Recursion
We can use the above rules to build the recursion.
2. Base case
When we run out of opened and closed parentheses, we have a valid solution, and we should add it to our array of solutions.
3. Code
Here's the recursive code:
To code this up, just combine the recurion and base case.
Time Complexity O(n⋅2n). The output array contains roughly 22n strings. Each of these strings is of size 2n. This means it takes 2n time to build each of these strings. We also build parentheses + "(" which takes 2n time, and parentheses + ")" which takes 2n time, giving a total of O(6n⋅22n) time.
Space Complexity O(n⋅2n) for the output array.
Call Stack Complexity O(n2). The Call Stack grows to size 2n. Each call stores its own O(n) sized string.
This recursion recurses on strings, which is slow. This is because when you say something like parentheses+"("
, the computer will create an entirely new string, since strings are immutable. Instead, it's better to use an Array instead.
We can also improve the memory usage of the function by using Backtracking. Backtracking is when we make the inputs to the function global so that we only have to store them a single time. We can store parentheses
as a global variable, so that we don't have to recreate it in every function call. We'll also make o
and c
global to go full force with Backtracking (even though it doesn't affect the time or space complexity).
Here's the code for this:
Time Complexity O(n⋅2n). More accurately, O(2n⋅22n). Each entry has 2n characters, and there are roughly 22n entries.
Space Complexity O(n⋅2n) for the output array. The Call Stack and global parameters also take up some space, but the output array's space complexity beats them by far.
Call Stack Complexity O(n). The Call Stack gets 2n calls deep, and each call uses O(1) space.