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