To generate every possible solution, we should start with the empty string "", and repeatedly add opened and closed parentheses until we visit every solution.

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

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