Recursion

All Parentheses

Backtracking

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

First Few Test Cases:

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\texttt{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:

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(n2n)O(n\cdot 2^n ). More accurately, O(2n22n)O(2n \cdot 2^{2n}). Each entry has 2n2n characters, and there are roughly 22n2^{2n} entries.

Space Complexity O(n2n)O(n\cdot 2^n ) 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)O(n). The Call Stack gets 2n2n calls deep, and each call uses O(1)O(1) space.

Mark as Completed:
Submits:
generateParentheses
Test your code to get an output here!
generateParentheses(
)
Test your code to get an output here!