# All Balanced Parentheses Strings

Print all strings consisting of `n`

balanced parentheses.

**Edit 2017-05-17.** Added implementation in Golang.

For example, the strings consisting of three balanced parentheses are the following.

**Input.** The input consists of a sequence of numbers, one on a
line of its own, followed by EOF. The following is an example input.

**Output.** For a given input, the output consists of one of more
sequences of balanced parentheses strings. Each sequence corresponds
to a number in the input. The sequences appear in the order
determined by the input numbers. Each sequence need not be sorted.
The strings that belong to a given sequence must not be repeated. For
example, the following is the output that corresponds to the previous
example input.

# Solution

The structure of any given string consisting of `n`

balanced
parentheses obeys the following three rules.

**Rule 1.** The first position in the string consists of an opening
parenthesis.

**Rule 2.** A given position in the string may consist of an opening
parenthesis when there are less than `n`

opening parentheses in the
previous positions. For example, consider the fourth position of
the following string.

The opening parentheses at the fourth position is
allowed because there are only 2 opening parentheses in prefix
`(()`

.

**Rule 3.** A given position in the string may consist of a closing
parenthesis when there is an unmatched opening parenthesis at some
previous position. For example, consider the fourth position of the
following string.

The closing parenthesis at position 3 is allowed because the opening
parenthesis in the first position is unmatched in prefix `(()`

.

Our approach to enumerating all balanced parentheses strings of length
`n`

consists in applying the rules from left to right until we output
`n`

pairs of parentheses and then backtracking at each position where
more than one option is possible. To illustrate our approach,
consider the following tree of rule applications for `n = 3`

.

Consider the path highlighted in red. The path leads to the following string.

The first position of the string corresponds to the first transition
from left to right and also to Rule 1. The second position may be an
opening or closing parenthesis, so we choose an opening parenthesis.
For the third position we have the same choices, so we choose a
closing parenthesis. Something similar happens for the fourth
position. At this point, the last two positions must be closing
parenthesis because we have used 3 opening parentheses and there are
two unmatched opening parentheses in prefix `(()(`

.

To apply the rules correctly, we remember the number of opening parenthesis still available and the number of unmatched opening parenthesis as we build each string from left to right. To illustrate the building of each string, we decorate each transition of our previous tree with the number of opening parenthesis available to the next node. On top of that number, we write the number of unmatched opening parenthesis for the next node.

Consider the transition highlighted in red. In that transition, number 2 indicates that there are 2 unmatched parentheses available to the next node and number 1 indicates that there is 1 more opening parenthesis available to the next node.

# Implementation

We implement the application of rules in Ruby and Golang.

Our Ruby implementation is the following.

Our Golang implementation is the following. You will find a corresponding Makefile here.

# Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.