1
$\begingroup$

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:

   ()()()
   ()(())
   (())()
   (()())
   ((()))
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – theyaoster Jun 15 '17 at 6:57
  • 1
    $\begingroup$ On this site, we describe algorithms as pseudocode. Not everybody can read Java, and besides the pseudocode will be dramatically shorter. $\endgroup$ – Yuval Filmus Jun 15 '17 at 7:42
  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 15 '17 at 17:31
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ @DavidRicherby We don't count space on the output tape. $\endgroup$ – Yuval Filmus Jun 15 '17 at 7:51
  • $\begingroup$ @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. $\endgroup$ – David Richerby Jun 15 '17 at 7:56
  • $\begingroup$ 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. $\endgroup$ – Mohemnist Jun 15 '17 at 8:39
  • $\begingroup$ The time complexity is the Catalan number so? I have seen people wrongly saying that is an exponential algorithm but I was not sure about that... and for this reason, I posted the question over here. @Mohemnist thanks en.wikipedia.org/wiki/Catalan_number This is the source geeksforgeeks.org/… $\endgroup$ – Sergio Jun 15 '17 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.