Space and time complexity of balanced parentheses enumeration algorithm Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string):

A(prefix):


If prefix contains $n$ right parens: print prefix and return.
If prefix contains more left parens than right parens: call A(prefix + ")").
If prefix contains less than $n$ left parens: call A(prefix + "(").


As an optimization, instead of counting the number of left and right parens at each step of the recursion, we carry them around (so A gets two more parameters, which are the number of parens of teach type in prefix).

For example, when $n = 3$, this outputs the following strings:

   ()()()
   ()(())
   (())()
   (()())
   ((()))
This is a simple enumeration algorithm. The space complexity is $O(n)$, and the time complexity is the size of the output, since you do not doing anything useless.

By the way, the number of rows in the Catalan number. $C_n=\frac 1 {n+1}\binom {2n} n$.