# 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):

1. If prefix contains $n$ right parens: print prefix and return.
2. If prefix contains more left parens than right parens: call A(prefix + ")").
3. 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:

   ()()()
()(())
(())()
(()())
((()))

• I understand that; it is just that it would be helpful if you provided details of the problem statement. For example, if you had provided the example you have edited in earlier, I probably wouldn't have misunderstood your code in my previous comment. – theyaoster Jun 15 '17 at 6:57
• On this site, we describe algorithms as pseudocode. Not everybody can read Java, and besides the pseudocode will be dramatically shorter. – Yuval Filmus Jun 15 '17 at 7:42
• What is your question? I don't see a question here, just a series of statements. This is a question-and-answer site, so it is important to be explicit about what question you want an answer to. – D.W. Jun 15 '17 at 17:31

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$.
• @YuvalFilmus I wasn't counting space on the output tape; I was counting space used on the work-tape to manage the recursion. (Except I miscounted it so I've deleted my comment.) Nonetheless, I think it would be helpful if the answer justified the $O(n)$ claim, if only for the benefit of those of us who've not yet had enough coffee. – David Richerby Jun 15 '17 at 7:56
• I see you deleted you code. The recursive function will run at most $2n$ nested levels to print a line. The memory of each function call is $O(1)$. Therefore, you're using an $O(n)$ space. – Mohemnist Jun 15 '17 at 8:39